Following up on a comment by sdcvvc I checked out example 11.7 in Computational Complexity: A Modern Approach by Arora and Barak (Draft of 2008). There, the authors describe a "PCP algorithm" for the problem Graph Non-Isomorphism (GNI):
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 \not\equiv 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(\langle\sigma(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.
- the algorithm uses $O(n \log n)$ random bits and queries $O(1)$ bits of $\pi$,
- $(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
- $(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
$\qquad\displaystyle \pi(\langle H \rangle) =
\begin{cases}
0 &, H \equiv G_0, H \not\equiv G_1 \\
1 &, H \equiv G_1, H \not\equiv G_0 \\
\text{arbitrary} &, \text{ otherwise}
\end{cases}$
where $H$ are all graphs with $n$ nodes. Since $G_0 \not\equiv G_1$ and
$\sigma(G_b) \equiv G_b$, we have $\sigma(G_b) \not\equiv 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
$\qquad\begin{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).
- 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.
