If Unknotting is NP-complete, then PH collapses to the second level.
As it turns out, this is a trivial corollary of an older result by Boppana, Håstad and Zachos that if co-NP has short interactive proofs, then PH collapses. Specifically if Unknotting is NP-complete, then Knotting is co-NP-complete and since it is in AM = IP(2), this implies that co-NP is in IP(2), and everything comes crashing down.
It would be nice if there was some way to augment the Complexity Zoo to make such results easier to find.
The multiplication of ill-motivated complexity classes in Theoretical Computer Science has got to be one of the ugliest bodies of work in all of science. I remember studying the subject with a kind of grim resolution that at some time something pretty or otherwise admirable would inevitably emerge from the many papers on this subject, but no, it's a mess from top to bottom, as far as I can tell. Ick, ick, ick! More ranting (as if anyone wants to read it!) at
ReplyDeletethis link
Posted by Thane Plambeck
I don't know. In a formal sense a lot of classes would collapse if P = NP, but my view of much of complexity theory is far less pessimistic. I view complexity classes to a great extent as metaphors. BPP is a statement of the power of randomization; NP of the difficult of finding vs verifying.
ReplyDeleteThere are admittedly many classes that are not as beautiful as some of these (and the existence of complete problems is usually one test for "beauty"), but every class has some interesting nuance that illuminates some interesting aspect of the complexity of a computation. If P = NP, it would almost be like destroying a beautiful varied jungle (or zoo), and replacing it by a single species (or a few).
Beauty is indeed in the eyes of the beholder.
Posted by Suresh
Perhaps someone can do to the complexity zoo what Murray Gell-Mann did for the particle zoo?
ReplyDeletePosted by Anonymous
To make the "Zoo" easier to "see" (rather than a linear alphabtetical list, one would need a nice view of the inclusion lattice. Johnson has a (large) chapter in the Handbook of TCS, at the end of which there are a number of diagrams showing different parts of the lattice (below P, above NP, etc.).
ReplyDeleteThere is the recent humongous picture that someone drew of the lattice, but it is a bit unwieldy to navigate.
As to ickiness, it's just chipping away at the problem when no one has a sledge hammer yet.
Posted by Mitch