Anatomy of a Theorem

A comment to Tuesday's post mentions the result

If Graph Isomorphism is NP-complete then the polynomial-time hierarchy collapses.

He gives credit to Schöning but this theorem combines results from a variety of papers.

Goldreich, Micali and Wigderson had a breakthrough paper with three main results.

1. If one way functions exist, every language in NP has a (cryptographic) zero-knowledge proof,
2. Graph Isomorphism has a statistical zero-knowledge proof (where the verifier learns nothing except that the graphs are isomorphic in an information-theoretic sense), and
3. Graph Non-Isomorphism has a bounded-round interactive proof.

It's the last result that we need. The protocol is rather simple.

Input: (G₁,G₂)
Verifier: Pick i∈{1,2} and a permutation π of the vertices uniformly at random. Let G=π(G_i).
Verifier→Prover: G
Prover→Verifier: j
Verifier: Accept if i=j.

If the two graphs are not isomorphic a powerful prover can determine which graph the verifier originally chose. If the two graphs were isomorphic the prover would only have a 1/2 probability to getting the answer right. We can lower the error with parallel repetition.

This protocol requires private coins that the verifier can flip but the prover can't see. Goldwasser and Sipser show how to convert any private-coin protocol to a public-coin protocol where the verifier flips the coins in front of the prover.

Babai and Moran show how to take any bounded-round public-coin protocol and create an equivalent protocol where the verifier flips random coins and the prover responds, the class AM.

Boppana, Håstad and Zachos (which combined two earlier papers) show that if co-NP is contained in AM then the polynomial-time hierarchy collapses to the second level.

Putting it all together, if graph isomorphism is NP-complete then graph non-isomorphism is co-NP-complete and we have co-NP in AM implying the hierarchy collapses.

Schöning gives a self-contained proof and shows that graph isomorphism is in the low hierarchy.

In my first STOC paper I show that for any language that has a statistical zero-knowledge proof, there is a bounded-round interactive proof for the complement of that language. Running through the same set of papers as above one gets that if NP-complete sets have statistical zero-knowledge proofs then the polynomial-time hierarchy collapses.