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.

- If one way functions exist, every language in NP has a
(cryptographic) zero-knowledge proof,
- 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
- Graph Non-Isomorphism has a bounded-round interactive proof.

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

**Input:** (G_{1},G_{2})

**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.