2
$\begingroup$

$\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.

Improve this question
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think I understand this system's Completeness. However, the proof also seems to deal with the soundness because it says "if G0≡G1, then the probability of accepting is at most 1/2". So it has to deal with the case when G0≡G1. Where does 1/2 come from? When G0≡G1, do they assign the bit 0 or 1 randomly so that random b has 1/2 chance to be equal to the assigned random bit? $\endgroup$ – Zachary HUANG Nov 18 '19 at 16:38
  • $\begingroup$ When $G_0 \equiv G_1$ we don't assign anything. Rather, we show that no assignment (i.e., no proof) convinces the verifier with probability better than 1/2. $\endgroup$ – Yuval Filmus Nov 18 '19 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.