Friday, February 04, 2005

Polynomial hierarchy collapse

Another thing that puzzled me about the Unknotting result was the corollary:

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.

Disqus for The Geomblog