Example for a non-trivial PCP verifier for an NP-complete problem

During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating

$\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$.

I understand the technical definition of a PCP verifier, so I know in principle what kind of algorithm has to exist for every NP problem: a randomised algorithm that checks $O(1)$ bits of the given certificate for the given input using $O(\log n)$ random bits, so that this algorithm is essentially a one-sided error Monte-Carlo verifier.

However, I have trouble imagining how such an algorithm can deal with an NP-complete problem. Short of reading the proof of the PCP theorem, are there concrete examples for such algorithms?

I skimmed the relevant sections of Computational Complexity: A Modern Approach by Arora and Barak (2009) but did not find any.

An example using a $\mathsf{PCP}(\_,\ll n)$ algorithm would be fine.

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.

StackExchange Computer Science Q#13246, answer score: 8