tag:blogger.com,1999:blog-3722233.post2377503315744331333..comments2019-11-16T02:09:32.154-05:00Comments on Computational Complexity: Mahaney's TheoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-65891072938215212252011-10-04T06:44:22.304-04:002011-10-04T06:44:22.304-04:00Thanks for that proof Lance! It's simpler tha...Thanks for that proof Lance! It's simpler than the one I used to teach; I will use this one from now on.<br />(Indeed, I think one should teach the theorem.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45518642172637625612011-09-27T20:32:09.427-04:002011-09-27T20:32:09.427-04:00Thomas: The proof you presented was given as a gu...Thomas: The proof you presented was given as a guided exercise in a complexity theory course taught by Manindra Agrawala at IITK. Though I don't remember Manindra saying this was due to him, I vaguely remember Somenath Biswas crediting it to him.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25795376159857668692011-09-26T10:05:20.811-04:002011-09-26T10:05:20.811-04:00Arne: Thanks. Fixed.Arne: Thanks. Fixed.Lancehttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44099791433996471832011-09-26T05:34:29.092-04:002011-09-26T05:34:29.092-04:00Thanks for the clarification!Thanks for the clarification!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15820066621291883772011-09-26T03:54:36.162-04:002011-09-26T03:54:36.162-04:00I think the sentence "Case 2: All the zi are ...I think the sentence "Case 2: All the zi are distinct. There are only m elements in A so w1 is not in A and a' cannot be between w0 and w1."<br />should be corrected to "... so z1 is not in A..."?Arne Meierhttp://www.thi.uni-hannover.de/~meiernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4148550516742850372011-09-25T11:33:28.483-04:002011-09-25T11:33:28.483-04:00I added a sentence clarifying that the only w we l...I added a sentence clarifying that the only w we look at are assignments. <br /><br />For Daveagp: Mahaney's theorem holds for NP-complete sets via Karp (many-one) reductions. We know the polynomial-time hierarchy collapses if there are sparse complete sets for Cook (aka Turing) reductions but the implication P = NP is unknown.Lancehttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49632757292938517202011-09-24T19:03:36.034-04:002011-09-24T19:03:36.034-04:00I think there is a bug in the sentence
"Ther...I think there is a bug in the sentence<br /><br />"There are only m elements in A so w1 is not in A and a' cannot be between w0 and w1."<br /><br />There are infinitely-many elements in A. I think you meant that there are m elements in the set { z : z = f(\phi, w) and w is an assignment to \phi }.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21957957619385778482011-09-24T05:38:08.545-04:002011-09-24T05:38:08.545-04:00There is a simpler proof of Mahaney's theorem ...There is a simpler proof of Mahaney's theorem (not due to me) via the well known tree pruning technique:<br /><br />Let f be a reduction from SAT to the sparse set S.<br />Given formula F.<br />Let m = |F|^k bound the number of strings in S up to |f(F)|.<br /><br />Develop the standard self-reduction tree of F<br />until we have formulas F_0, F_1, ..., F_{m+1}.<br />We show that we can prune one of them.<br />The invariant we want to maintain is:<br />if F in SAT then one of the formulas we keep in the tree is in SAT.<br /><br />Consider the sequence of strings<br /><br /> f(F_0 or F_1), f(F_0 or F_2), ..., f(F_0 or F_{m+1})<br /><br />- if they are pairwise different,<br /> then F_0 is not in SAT and we can prune F_0.<br />- if 2 are equal, say f(F_0 or F_i) = f(F_0 or F_j),<br /> then we can prune F_i:<br /> if F_i is in SAT then also F_0 or F_j is in SAT.<br /><br />Now go on extending the tree on the remaining formulas and do pruning.Thomashttps://image.informatik.htw-aalen.de/Thierauf/index.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30305832455080872162011-09-23T19:48:19.682-04:002011-09-23T19:48:19.682-04:00I have a question, possibly dumb: you say (φ,w) is...I have a question, possibly dumb: you say (φ,w) is in B iff f(φ,w) is in A; but doesn't this assume a particular kind of reduction (Karp?), not a general reduction (Turing?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34628932878175041352011-09-23T17:56:50.465-04:002011-09-23T17:56:50.465-04:00Locally in Buffalo, the question of extending Maha...Locally in Buffalo, the question of extending Mahaney's Theorem to classes within NC---"how low can it go?"---such as in <a href="http://pages.cs.wisc.edu/~jyc/papers/NL.pdf%22" rel="nofollow">this paper</a> led to further consideration of other properties of these low-level classes.<br /><br />Moreover, "sparse" got generalized to other notions of "low information content".<br /><br />(Word verification first gave me "strat". I am not a pure Strat, but rather an Oxfordian semi-collaborationist.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44202924233248241722011-09-23T16:35:20.246-04:002011-09-23T16:35:20.246-04:00Although sparsity is sometimes not terribly well-m...Although sparsity is sometimes not terribly well-motivated, it is definitely not a "random" property.<br /><br />1. NE = E is *equivalent* to all sparse NP sets being contained in P. (This is a result of Hartmanis, Immerman, and Sewelson.) So questions about sparse NP sets are strongly related to questions about NEXP.<br /><br />2. NP has polynomial size circuits iff NP is polytime Turing-reducible to a sparse set, i.e., NP is in P^{S} for a sparse S. So questions about reducibility to sparse sets are related to questions about polynomial size circuits.<br /><br />But I still am not sure I would teach Mahaney's theorem :)ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48624948569170930062011-09-23T15:16:10.526-04:002011-09-23T15:16:10.526-04:00Lance, I don't find your answer very satisfyin...Lance, I don't find your answer very satisfying. <br /><br />One can define all kinds of (random) properties about NP-complete sets, and spend the whole semester proving things about them. Why should anyone care about sparseness in particular? (If not b/c of the isomorphism conjecture.) Why would one think, a priori, that NP-complete sets could be sparse?<br /><br />And what do you think <em>is</em> taught in courses (or books) that should be taken out to make room for Mahaney?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36420353574195933502011-09-23T11:09:14.711-04:002011-09-23T11:09:14.711-04:00The statement of Mahaney's theorem is to me as...The statement of Mahaney's theorem is to me as interesting as that of Ladner's theorem. The simplified proof above is nice and could be given as a guided exercise.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10049735919996131992011-09-23T10:12:21.233-04:002011-09-23T10:12:21.233-04:00NP-completeness is the most important concept of a...NP-completeness is the most important concept of all of theoretical computer science and Mahaney gives us a fundamental limitation on what these NP-complete sets can look like.Lancehttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23518475871770562932011-09-23T09:54:07.739-04:002011-09-23T09:54:07.739-04:00Lance (or anyone else): is there any argument to t...Lance (or anyone else): is there <em>any</em> argument to teach Mahaney's theorem (other than as a time filler)?<br /><br />As I understand it, Mahaney's theorem was interesting at the time because of its relation to the isomorphism conjecture. But Mahaney would have only really shed light on the conjecture if he had proven the opposite, and anyway most people now believe the isomorphism conjecture is false. So why teach Mahaney's theorem in an intro course?<br /><br />I'm not saying we should forget about it, I'm just saying that as more knowledge accumulates some things have got to go from an intro course.Anonymousnoreply@blogger.com