tag:blogger.com,1999:blog-3722233.post114200244530721614..comments2024-10-07T03:56:38.595-05:00Comments on Computational Complexity: On P versus NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger35125tag:blogger.com,1999:blog-3722233.post-1142855476504684672006-03-20T05:51:00.000-06:002006-03-20T05:51:00.000-06:00But Scott, he/she "generates random research paper...But Scott, he/she "generates <B>random</B> research papers". Doesn't it put the suggestion on randomized complexity classes?Osiashttps://www.blogger.com/profile/08739473119362234947noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142320026418459152006-03-14T01:07:00.000-06:002006-03-14T01:07:00.000-06:00Solving P?=NP is actually trivial.Get yourself a c...Solving P?=NP is actually trivial.<BR/><BR/>Get yourself a computer, get that package that generates random research papers, feed it all of the known stuff in complexity and computability. Run it iteratively until you get the answer.<BR/><BR/>I think there are plenty of people on the internet that have demonstrated a head-start in this approach.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142252159507294382006-03-13T06:15:00.000-06:002006-03-13T06:15:00.000-06:00>>Well, you have simply re-defined >>the problem, ...>>Well, you have simply re-defined <BR/>>>the problem, again at a high <BR/>>>level of abstraction.<BR/><BR/>Redefined? Check this link: <BR/><BR/>http://weblog.fortnow.com/2002/12/foundations-of-complexitylesson-10-p.htmlOsiashttps://www.blogger.com/profile/08739473119362234947noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142230957500590992006-03-13T00:22:00.000-06:002006-03-13T00:22:00.000-06:00Anonymous said ...>>Your comments prove that you d...Anonymous said ...<BR/>>>Your comments prove that you do not even have a basic knowledge of the classes P and NP. <<<BR/><BR/>A strong indictment, indeed. Undoubtedly, justified to large extent. <BR/><BR/>However, even though this poster has decided to close shop on the issue here, in view of his observations, some may want to take a glance at this, foundational, analysis of the validity of the PvsNP problem, when expressed in set-theoretical terms?<BR/><BR/>http://alixcomsi.com/CTG_06_Consequences.htm<BR/>#Endnote_7_3_P_vs_NP<BR/><BR/>It is Para III(3.6) on p70 of the associated pdf file.<BR/><BR/>BhupAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142230141883886382006-03-13T00:09:00.000-06:002006-03-13T00:09:00.000-06:00Can someone better explain this result? If L(T) is...<I>Can someone better explain this result? If L(T) is empty, then why isn't P^{L(T)} = P (and similarly for NP)?</I><BR/><BR/>The problem is that, assuming there exists a proof of either direction of P vs. NP, there's no way to actually prove that L(T) actually is the empty set; that L(T) is empty (and thus P^{L(T)}=P) would be an unprovably true statement in the model. (the type that Godel's theorem says exist)<BR/><BR/>Note, also, that this is a "fix a formal model and..." theorem, so it make sense to say that L(T) actually *is* empty, in the same way it makes sense to say that the unprovably true statement constructed in Godel's theorem is actually true.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142217200431918652006-03-12T20:33:00.000-06:002006-03-12T20:33:00.000-06:00The most interesting result I've seen along these ...<EM>The most interesting result I've seen along these lines is that you can pick a turing machine T such that P^(L(T)) vs. NP^(L(T)) has no proofs of either equality or inequality, and L(T) is empty.</EM><BR/><BR/>Can someone better explain this result? If L(T) is empty, then why isn't P^{L(T)} = P (and similarly for NP)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142212493560913492006-03-12T19:14:00.000-06:002006-03-12T19:14:00.000-06:00Bhup: Your comments prove that you do not even hav...Bhup: Your comments prove that you do not even have a basic knowledge of the classes P and NP. The following is one of many gems:<BR/><I><BR/>Since Goedel has shown that we can actually construct an expression for R(x), we thus have, under the assumed thesis, a well-defined, constructible, relation, R(x), that must be in NP.<BR/></I><BR/><BR/>Have you even bothered to read a textbook on complexity ? Maybe you did and you're still spouting this nonsense ... that's even more disturbing.<BR/><BR/>I think you ought to know that the academia welcomes iconoclasts ... they have a strong objection to charlatans, though. <BR/><BR/>I sincerely hope you realize how ridiculous your posts are. I suggest you spend some time reading up these topics (actually understanding them) before you try to be the new Goedel incarnate. It is very easy to come up with BS theories especially about things you have no knowledge of.<BR/><BR/>This is going to be my last response to you because this discussion is a waste of time and space.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142209323820177322006-03-12T18:22:00.000-06:002006-03-12T18:22:00.000-06:00====================Osias said... >>What? Here is ...====================<BR/>Osias said... <BR/>>>What? Here is a intuitive "grasp": Is there a eficient method to find a solution for a problem whose solutuion is eficiently (poly) verifiable?<<<BR/><BR/>Well, you have simply re-defined the problem, again at a high level of abstraction.<BR/><BR/>This is far removed from the consensus of a minimum, common, intuition upon which axiomatic languages are attempted to be founded.<BR/><BR/>What I would argue, however, is that a thesis such as, for instance:<BR/><BR/>A true, total, arithmetical formula is Turing-computable if, and only if, it is PA-provable.<BR/><BR/>is, like the Church-Turing Theses, much nearer our intuition.<BR/><BR/>The concepts of 'true', 'total', 'arithmetical', 'Turing-computable', 'PA-provable' are, mathematically, far more elementary than those that occur in the standard, Cook's, formulation of the PvsNP problem.<BR/><BR/>Now, it is elementary to conclude from the above thesis that, if R(x) is a true arithmetical relation that is not provable from the axioms of first-order Peano Arithmetic, then R(x) cannot, itself, be Turing computable. <BR/><BR/>Hence, it is not in the class P.<BR/><BR/>However, since it is true for all natural numbers, then, assuming Church's Thesis, it follows that there is an instantiationally equivalent recursive relation which is Turing-computable.<BR/><BR/>Since Goedel has shown that we can actually construct an expression for R(x), we thus have, under the assumed thesis, a well-defined, constructible, relation, R(x), that must be in NP.<BR/><BR/>Whether this argument is eventually validated or not, I would consider it as providing a more intuitive 'grasp' of the PvsNP problem mathematically.<BR/><BR/>Anonymous said... <BR/>>> ...it is indeed sad to see you out there wasting your wisdom commenting on random blogs. <BR/><BR/>You should seek out more appropriate avenues...<< <BR/><BR/>Easier said than done, if you are not in an academic environment. I have, indeed, occasionally sent a paper to a refereed journal.<BR/><BR/>In all of them, my explicit thesis is that, if we introduce effective methods of determining the satisfiability, and truth, of the formulas of a formal system, under a given interpretation, into Tarski's (commonly accepted) definitions, then the consequences contradict standard interpretations of, for instance, Goedels formal reasoning, the Church-Turing theses, Turing's Halting Theorem, Cantor's Theorem, etc.<BR/><BR/>The referees remarks have generally included a phrase such as, "It is known that ...", where the reference is to some standard interpretation of the formal reasoning which, actually, is my starting point!<BR/><BR/>That is why I concluded that my iconoclastic interpretations of classical theory may require a paradigm shift that, by Kuhn's definition, is essentially unpredictable.<BR/><BR/>Hence my attempt to reach out to similar viewpoints through discussion forums, and what you see as 'random' blogs.<BR/><BR/>I see these, however, as the harbingers of an environment that nurtures the initial steps of iconoclastic thought, without the danger of attempting to harness it prematurely under the unavoidable pressures of academic refereeing.<BR/><BR/>Regards,<BR/><BR/>BhupAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142208254771261972006-03-12T18:04:00.000-06:002006-03-12T18:04:00.000-06:00I got it out of Du and Ko, but it came from a 1976...I got it out of Du and Ko, but it came from a 1976 paper by Hartmanis and Hopcroft. ("Hartmanis, J. and Hopcroft, J. [1976], Independence results in computer science, ACM SIGACT News 8(4), 13-23")Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142203005650297182006-03-12T16:36:00.000-06:002006-03-12T16:36:00.000-06:00David Klempner wrote: The most interesting result ...David Klempner wrote: <EM>The most interesting result I've seen along these lines is that you can pick a turing machine T such that P^(L(T)) vs. NP^(L(T)) has no proofs of either equality or inequality, and L(T) is empty. (L(T) is the language computed by T)</EM><BR/><BR/>David, do you recall the authors/title of that result?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142202518102105782006-03-12T16:28:00.000-06:002006-03-12T16:28:00.000-06:00I was wondering if there have been any attempts to...<I>I was wondering if there have been any attempts to prove the impossibility of asserting either P!=/=NP.</I><BR/><BR/>The most interesting result I've seen along these lines is that you can pick a turing machine T such that P^(L(T)) vs. NP^(L(T)) has no proofs of either equality or inequality, and L(T) is empty. (L(T) is the language computed by T)<BR/><BR/>The proof is a straightforward diagonalization against proofs argument and the result itself doesn't say anything at all about P vs. NP, but it's rather interesting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142197619366622602006-03-12T15:06:00.000-06:002006-03-12T15:06:00.000-06:00Yes, there is, but I didn't understand them when I...Yes, there is, but I didn't understand them when I read...Osiashttps://www.blogger.com/profile/08739473119362234947noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142122814563661192006-03-11T18:20:00.000-06:002006-03-11T18:20:00.000-06:00As misguided as it is, the previous comment remind...As misguided as it is, the previous comment reminds me of the issue that there are two very different uses of the term 'one-way function' in the complexity literature: <BR/><BR/>The first has the requirement that the inversion problem be 'hard on average' when given the function applied to a pre-image chosen uniformly at random. This is the really important definition for cryptographic applications.<BR/><BR/>The second, which has some applications in structural complexity (cf. the Berman-Hartmanis conjecture), requires that the function be hard to invert in the worst case.<BR/><BR/>It often seems that people with a minimal understanding of P vs NP confuse the two definitions. A very nice way to understand how the former fits is Russell Impagliazzo's <A HREF="http://www.cs.ucsd.edu/~russell/average.ps" REL="nofollow">personal view of average case complexity</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142121987330634822006-03-11T18:06:00.000-06:002006-03-11T18:06:00.000-06:00SighSighAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142119002327414932006-03-11T17:16:00.000-06:002006-03-11T17:16:00.000-06:00The P /= NP problem is ill-posed.Opposite to one-w...The P /= NP problem is ill-posed.<BR/>Opposite to one-way function is<BR/>two-way function. But has anyone<BR/>defined exactly what is a two-way<BR/>function? Between one-way function<BR/>and two-way function there is<BR/>gradation of onewayness which msut<BR/>be measured. We lack such a measure. If one-way function has<BR/>no absolute existence then how<BR/>do we prove its existence? HuenYKAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142106556449803832006-03-11T13:49:00.000-06:002006-03-11T13:49:00.000-06:00I am surprised at these comments. We as a communit...I am surprised at these comments. We as a community should be happy by such a workshop. The fact that our problems draw the interest of mathematicians is a good thing. Whether or not there is anything particularly promising at their current approach is beside the point (by the way, do we have any particularly promising direction?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142098891065481122006-03-11T11:41:00.000-06:002006-03-11T11:41:00.000-06:00http://alixcomsi.com/index01.htmThis one looks int...<EM>http://alixcomsi.com/index01.htm<BR/></EM><BR/><BR/>This one looks interesting enough for Kurt Godel to stir in his grave: <EM>G�del�s Incompleteness Theorems hold vacuously</EM>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142079598927206562006-03-11T06:19:00.000-06:002006-03-11T06:19:00.000-06:00>>It's much easier than you'd think.As a "I-don't-...>>It's much easier than you'd think.<BR/><BR/>As a "I-don't-understand-most-logic-but-I-know-how-to-program"-guy, I could add:<BR/><BR/>If the paper tells P=NP, have they implemented and run their algorithm to see "oh, how fast!!!"?Osiashttps://www.blogger.com/profile/08739473119362234947noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142078150654209902006-03-11T05:55:00.000-06:002006-03-11T05:55:00.000-06:00>difficulty of even getting an >intuitive grasp of...>difficulty of even getting an <BR/>>intuitive grasp of the PvsNP <BR/>>problem<BR/><BR/>What? Here is a intuitive "grasp": Is there a eficient method to find a solution for a problem whose solutuion is eficiently (poly) verifiable?Osiashttps://www.blogger.com/profile/08739473119362234947noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142059124229018302006-03-11T00:38:00.000-06:002006-03-11T00:38:00.000-06:00http://alixcomsi.com/index01.htmMost of the articl...http://alixcomsi.com/index01.htm<BR/><BR/>Most of the articles here are cutting-edge articles in the exciting area of philosophical complexity theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142058385319119092006-03-11T00:26:00.000-06:002006-03-11T00:26:00.000-06:00Bhup: as author of several published proofs on the...<EM> Bhup: as author of several published proofs on these non-polynomial space/time/Piano/Zorn issues ...</EM><BR/><BR/>Where, pray, may I ask are these articles? I could not find any of his articles on the web, nor does he have a DBLP entry.<BR/><BR/>I could not understand much after reading his lengthy discourses...I was hoping his papers would shed more light on the seminal issues that he discussed.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142054160293600862006-03-10T23:16:00.000-06:002006-03-10T23:16:00.000-06:00Bhup: as author of several published proofs on the...Bhup: as author of several published proofs on these non-polynomial space/time/Piano/Zorn issues it is indeed sad to see you out there wasting your wisdom commenting on random blogs. <BR/><BR/>You should seek out more appropriate avenues ... I'm sure a position for a pseudo-mathematician will be opening up real soon.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142046373321411022006-03-10T21:06:00.000-06:002006-03-10T21:06:00.000-06:00====================The criticism that my lengthy ...====================<BR/>The criticism that my lengthy discourse may promote illusions that it shouldn't is fair.<BR/><BR/>However, to make finer distinctions that avoid all illusions might just obscure the point - about 'out-of-the-box' thinking - that I intended.<BR/><BR/>Perhaps some clarifications may help place my looser comments in better perspective.<BR/><BR/>We know that a non-deterministic Turing machine can always be simulated by a deterministic Turing machine. <BR/><BR/>I was only attempting to distinguishing between the computations of a NDTM, if any, that increase exponentially in time, but not in any discernible manner, when simulated on a DTM, as 'chaotic', and those that do not as 'regular'.<BR/><BR/>There was no intent to claim that the class NP is identically the 'chaotic' computations, or that the class P is identically the 'regular' computations. <BR/><BR/>If the overall direction of my scenario is, indeed, significant to the PvsNP issue, then provable relations between these concepts would, of course, require to be established.<BR/><BR/>Since I have not attempted this, I do not know whether it is even possible.<BR/><BR/>There was also no intent to suggest that the term 'chaotic', as used here, should be understood as a precisely defined term of chaos theory.<BR/><BR/>My apologies if it is found misleading. The term 'irregular' would do as well.<BR/><BR/>My simplistic remarks on complexity and computability are, again, probably not germane to my overall thesis, and can be dismissed as suggested. Any confusion is regretted.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142046151838788062006-03-10T21:02:00.000-06:002006-03-10T21:02:00.000-06:00One thing is certainly clear from all this: Mr. Bh...One thing is certainly clear from all this: Mr. Bhupinder Singh Anand has way too much time on his hands :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142041229864472212006-03-10T19:40:00.000-06:002006-03-10T19:40:00.000-06:00It must be said:Please, let no one come away from ...It must be said:<BR/><BR/>Please, let no one come away from Anand's screed under the illusion that 'NP' stands for 'non-polynomial time' (it doesn't), or that it's an open question whether there are decidable problems requiring super-polynomial time (we know there are).<BR/><BR/>Referring to all non-polynomial algorithms as 'chaotic' is a conceptual mishmash without any justification. You can't make bold unifications of different theories just by proposing that their vocabularies be conflated. Complexity and computability are also being brazenly confused here.Anonymousnoreply@blogger.com