tag:blogger.com,1999:blog-3722233.post112657447191922640..comments2020-02-19T03:43:18.369-05:00Comments on Computational Complexity: Favorite Theorems: NP-Incomplete SetsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-12862722873166855302009-03-18T09:55:00.000-04:002009-03-18T09:55:00.000-04:00I am also not (even after Lance's answer to a ...I am also not (even after Lance's answer to a previous comment on this point) convinced by the claim that "we can compute f(n) in time polynomial in n". <BR/>If M_i(x) runs in time |x|^i and |x| < log n this gives the bound (log n)^i. But i is not a constant - it is a function of n. If i stays close to n (which seems likely since "most" TM's will disagree with L on a short input word so i will almost always be incremented) the bound becomes (log n)^n, which doesn't look very polynomial! Sorry if I am being stupid here, but a slightly more detailed explanation of this would be much appreciated. (I find it easier to believe that f(n) can be computed in time is polynomial in f(n), which I think suffices for the rest of the proof, at least with a little more work.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35149296179825100542007-09-08T03:23:00.000-04:002007-09-08T03:23:00.000-04:00Don't you need that the enumeration of the machine...Don't you need that the enumeration of the machines M_i can be done not only effectively, but even quickly, given i?<BR/>-- OK, but this is easily possible, no problem. <BR/>Thanks for responding to my comment. I like your write-up,<BR/>it makes several points more clear compared to the other places where you find the proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74416127582424791032007-09-05T09:45:00.000-04:002007-09-05T09:45:00.000-04:00We did make the assumption that M_i(x) runs in tim...We did make the assumption that M_i(x) runs in time at most |x|^i. That's enough to make sure we can compute f(n) quickly.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71678131087305780952007-09-05T09:04:00.000-04:002007-09-05T09:04:00.000-04:00I think there is a problem with the proof in Lance...I think there is a problem with the proof in Lance's write-up: "we can compute f(n) in time polynomial in n": I do not understand why<BR/>f(n) can be computed in polynomial time in n. E.g., we have to produce and simulate <BR/>M_i on small inputs x to determine f(n). Even if x is very small, how do you do that without further assumptions on the enumeration of the M_i?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126676299344416862005-09-14T01:38:00.000-04:002005-09-14T01:38:00.000-04:00While Ladner's result is wonderful, and the proof ...While Ladner's result is wonderful, and the proof (as attested by some<BR/>comments) far from trivial, it is much less satisfactory, and I would say,<BR/>less important than the corresponding result in Computability Theory, the<BR/>Friedberg-Muchnik Theorem.<BR/><BR/>The reason is that Ladner's proof gives us very little insight to the<BR/>fundamental problems, beyond its statement. In other words, there are no<BR/>fundamentally new techniques in its current proof(s). In contrast, the<BR/>Friedberg-Muchnik Theorem introduced the Priority Method, that is THE<BR/>major tool in "classical" Computability Theory.<BR/><BR/>More precisely, Friedberg and Muchnik had to overcome a huge technical problem.<BR/>The major tool to obtain negative results in Computability is to use<BR/>diagonalization. The standard trick can be described as follows:<BR/><BR/>make a (usually infinite) list of <B>requirements</B> (in the usual<BR/>diagonalization proof the requirements are "the function I want to define has<BR/>to be different from f_i , the i-th function on the list")<BR/><BR/><BR/>for each i, find an input w(i) ("the i-th witness") such that w(i) shows that<BR/>the i-th requirement has been satisfied (in the standard diagonalization proof<BR/>w(i)=i and we define the diagonal function D so that D(i) != f_i (i)<BR/><BR/>It is not very hard to show that if we write down the requirements that a c.e.<BR/>set not be complete, and want to satisfy the requirements by diagonalization,<BR/>and want the function w(i) to be computable, we will construct a set that is<BR/>decidable.<BR/><BR/>So, using the only tool available before Friedberg, we always obtain either<BR/>decidable or complete c.e. sets.<BR/><BR/>The big new insight was that the witness does not have to be computable in<BR/>order to get a proof--it can be a c.e. process if one defines it carefully.<BR/><BR/>It would be great to obtain a similarly useful tool by looking at incomplete<BR/>sets in NP -- even if the tool was not powerful enough to settle the P vs NP<BR/>question.Janos Simonhttps://www.blogger.com/profile/15677985672817404601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126658875410427662005-09-13T20:47:00.000-04:002005-09-13T20:47:00.000-04:00Yes, Papadimitriou's proof is a little different. ...Yes, Papadimitriou's proof is a little different. There, he proceeds by running each stage for at most n steps (rather than checking whether (log n)^{f(n)} \geq n, which I find sort of un-intuitive).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126643251318774032005-09-13T16:27:00.000-04:002005-09-13T16:27:00.000-04:00I think Lance's proof is rather clear, but perhaps...I think Lance's proof is rather clear, but perhaps a bit too telegraphic for people who are not too familiar with the subject. <BR/><BR/>Here's a roadmap of the proof:<BR/><BR/>We want a language L that is neither polynomial nor NP-complete. For the first part we need to diagonalize away from all polynomially recognizable languages, hence our language won't be in P. For the second we need to diagonalize away from all possible polynomial Turing reductions, thus precluding the posibility of SAT <= L. Hence L won't be NP complete.<BR/><BR/>For the first part, we enumerate all polynomial machines and diagonalize away from them. For the second part we enumerate all reduction functions f and diagonalize away from them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126638535218674252005-09-13T15:08:00.001-04:002005-09-13T15:08:00.001-04:00Anyone know of any good writeups of Ladner's proof...<I><BR/> Anyone know of any good writeups of Ladner's proof? </I><BR/><BR/>Lance also has a mini-writeup in his "Diagonalization" paper that may be more useful. I don't know how much more intuitive you can get though.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126638504232994742005-09-13T15:08:00.000-04:002005-09-13T15:08:00.000-04:00I think Papadimitriou's '94 text does a decent job...I think Papadimitriou's '94 text does a decent job, as well as being a great complexity theory resource more generally.Andynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126636859917636182005-09-13T14:40:00.000-04:002005-09-13T14:40:00.000-04:00Anyone know of any good writeups of Ladner's proof...Anyone know of any good writeups of Ladner's proof? (Sorry, Lance, but I didn't find your writeup very intuitive...)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126623265971428432005-09-13T10:54:00.000-04:002005-09-13T10:54:00.000-04:00P=NP implies the PH collapses (to P). But from P ...P=NP implies the PH collapses (to P). <BR/>But from P != NP it is *not* known to follow that the PH is infinite; indeed there are oracle worlds relative to which the hierarchy is strict up to any desired level, then collapses to that level (see 'The Complexity Theory Companion' and its Ch. 8 references).<BR/><BR/>To back you up on the other query, I can't find any evidence of GI's intractibility in Schoening et al.'s book on GI. It's hard to imagine what kind of conclusions could be drawn from GI in P, other than some other iso- type problems being in P too.<BR/><BR/>One (somewhat dubious) form of evidence that one might be able to produce:<BR/><BR/>Define a problem S[A] that is in NP^A relative to an arbitrary oracle A.<BR/><BR/>Show that with A random, then w/ prob. 1, S[A] is neither in P^A nor NP^A-complete.<BR/><BR/>Hope that this suggests S[�] is neither in P nor NP-complete. But this might fall flat. ?Andy Druckernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126621350521234952005-09-13T10:22:00.000-04:002005-09-13T10:22:00.000-04:00Actually, it should be "Schoening".When there is a...Actually, it should be "Schoening".<BR/>When there is an umlaut on a letter x, you can replace the letter with "xe".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126615842168098122005-09-13T08:50:00.000-04:002005-09-13T08:50:00.000-04:00Follow up to my previous comment: It should be Sch...Follow up to my previous comment: It should be Schoning. Also, the result doesn't preclude the possibility that GI is in P. In fact, I can think of no good "evidence" that GI is <I>not</I> in P other than the fact that no one has found an algorithm for it. Does anyone know of any results in this direction?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126615660513761202005-09-13T08:47:00.000-04:002005-09-13T08:47:00.000-04:00If P does not equal NP, then Graph isomorphism is ...<I>If P does not equal NP, then Graph isomorphism is NP-incomplete.</I><BR/><BR/>Someone correct me if I'm wrong, but I think this is already known: it should be the contrapositive of a result due to Schonig (1988) which states that if GI is NPC, then PH collapses to the second level.<BR/><BR/>If P != NP then the entire PH is infinite and so PI_2 != SIGMA_2 thus we have that GI is *not* NPC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126599593352627742005-09-13T04:19:00.000-04:002005-09-13T04:19:00.000-04:00Hi Lance, your last point is interesting. Why do ...Hi Lance, your last point is interesting. Why do you believe that there will be no other way to show the existence of incomplete sets, short of proving that P does not equal NP? <BR/><BR/>For example... are there reasons to believe that we cannot prove a statement like:<BR/><BR/>If P does not equal NP, then Graph isomorphism is NP-incomplete.<BR/><BR/>?Anonymousnoreply@blogger.com