[Solved]: Example for a non-trivial PCP verifier for an NP-complete problem

Input: Two graphs $G_0$ and $G_1$ with $n$ vertices each. Output: Accept if and only if $G_0$ and $G_1$ are not isomorph (write $G_0 notequiv G_1$).

We denote the certificate (they call it “proof”) by $pi$ and with $pi(i)$ the $i$-th bit of $pi$. The algorithm $A$ proceeds as follows:

• Choose a bit $b in {0,1}$ uniformly at random.
• Choose a permutation $sigma in S_n$ (of the vertices of $G_b$).
• Accept if $pi(langlesigma(G_b)rangle) = b$, reject otherwise.

Here, $langle _ rangle$ is some computable bijection from $mathbb{N}^n$ to a suitable range $[0..N] subseteq mathbb{N}$. We assume that if the derefenced bit in $pi$ does not exist, i.e. the certificate is too short, we reject. Claim: By above algorithm, GNI is in $operatorname{PCP}(n log n, 1)$, i.e.

1. the algorithm uses $O(n log n)$ random bits and queries $O(1)$ bits of $pi$,
2. $(G_0, G_1) in mathrm{GNI}$ implies that there is some certificate $pi$ so that $Pr[A(G_0, G_1, pi) text{ accepts}] = 1$, and
3. $(G_0, G_1) notin mathrm{GNI}$ implies that $Pr[A(G_0, G_1, pi) text{ rejects}] geq tfrac{1}{2}$ for all certificates $pi in {0,1}^*$.

Ad 1: Clear from the algorithm by noting that uniform permutation sampling is possible with $approx n log n$ random bits¹. Ad 2: Consider the certificate $qquaddisplaystyle pi(langle H rangle) = begin{cases} 0 &, H equiv G_0, H notequiv G_1 1 &, H equiv G_1, H notequiv G_0 text{arbitrary} &, text{ otherwise} end{cases}$ where $H$ are all graphs with $n$ nodes. Since $G_0 notequiv G_1$ and $sigma(G_b) equiv G_b$, we have $sigma(G_b) notequiv G_{1-b}$ for all $b$ and $sigma$. The query to $pi$ therefore always yields $b$ and thus always accept. Ad 3: Let $pi in {0,1}^*$ arbitrary and $H = sigma(G_b)$ the chosen query graph. If our query hits a non-existing bit of $pi$ we reject by assumption, which is correct. Otherwise, we calculate $qquadbegin{align} Pr[text{accept}] &= Pr[b=0] cdot frac{#[pi(H) = 0 mid H equiv G_0]}{#[H equiv G_0]} + Pr[b=1] cdot frac{#[pi(H) = 1 mid H equiv G_1]}{#[H equiv G_1]} &= frac{1}{2} cdot left( frac{#[pi(H) = 0 mid H equiv G_0]}{#[H equiv G_0]} + frac{#[pi(H) = 1 mid H equiv G_0]}{#[H equiv G_0]} right) &= frac{1}{2} end{align}$ using that $H equiv G_1 iff H equiv G_0$ in this case. Thus, the claim is proven. Some observations that helped me grasp these concepts better.

• The certificate $pi$ can be arbitrarily long and arbitrarily complex. Note that “good” certificates for the above algorithm essentially solve the same problem as the algorithm (many times).
• But that does not imply that any decision problem can be solved in PCP style by “just providing the answer in the certificate”. Condition 3 prevents any naive attempt of that kind.
• It is in general not possible to derive an efficient (randomised one-sided-error) algorithm that guesses the certificate (as is the case for NP-certificate verifiers).

1. Strictly speaking, this assumes that $n!=2^k$ (which of course almost never holds) since we have infinite worst-case runtime for other $n$. However, Arora/Barak seem to ignore this aspect.