Interactive proof system for graph nonisomorphism

Question

$\mathit{GNI} \in \mathrm{PCP}(\mathit{poly}(n),1)$

GNI is the language of nonisomorphic graphs. Given two grapsh $G_0$ and $G_1$ with $n$ vertices, a verifier expects $\pi$ to contain, for each labeled graph $H$ with $n$ vertices, a bit $\pi[H] \in \{0,1\}$ corresponding to whether $H \equiv G_0$ or $H \equiv G_1$ (arbitrary if neither case holds). Then the verifier can pick a random bit $b \in \{0,1\}$ and a random permutation of $G_b$, $H$. The verifier accepts iff the corresponding bit of $\pi[H]$ is $b$. If $G_0 \not\equiv G_1$ then the verifier accepts with probability $1$ while if $G_0 \equiv G_1$, then the probability of accepting is at most $1/2$.

I was reading this slide and got confused about the following part:

A bit $\pi[H]\in\{0,1\}$ corresponding to whether $H=G_0$ or $H=G_1$ (arbitrary if neither case holds)

But what if both cases hold? In that case, $G_0$ and $G_1$ are isomorphic, and how should we assign the bit? I hope that there's an example.

Answer 1

The slide describes a proof system for graph non-isomorphism. This is a way for the prover to convince the verifier that the two graphs are non-isormorphic. The soundness of this proof system derives from the fact that it cannot work if the graphs are isomorphic. If $G_0 \equiv G_1$ then no matter what the prover does, the acceptance probability is only $1/2$.

How should we assign the bit? Proof systems don't work in this way. A proof system has two guarantees:

• Completeness: if the input belongs to the language (in this case, the two graphs are not isomorphic), then there is a proof that convinces the verifier.

• Soundness: if the input doesn't belong to the language (in this case, the two graphs are isomorphic), then no proof convinces the verifier.

When proving these two properties of the proof system, we specify a proof only in the first case. In the second case we have to show, instead, that no proof works. It's a different quantifier:

• Completeness: if $G_0 \not\equiv G_1$ then there exists a proof which convinces the verifier with probability 1. (When proving completeness, we need to specify the proof that convinces the verifier.)

• Soundness: if $G_0 \equiv G_1$ then all proofs convince the verifier with probability 1/2. (When proving soundness, we don't need to specify a proof. Indeed, we need to show that all proofs perform badly. In a sense, a proof is given to us, and we have to show that it doesn't convince the verifier.)