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

Question

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.

Answer 1

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.

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

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

---

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.

Answer 2

Two problems that might help develop intuition:

1. Prove that $\mathsf{AM} \subseteq \mathsf{PCP}(\text{poly}(n),1)$. You are allowed to assume $\mathsf{NP} \subseteq \mathsf{PCP}(\text{poly}(n),1)$.

2. Prove that $\mathsf{PSPACE} \subseteq \mathsf{PCP}(\text{poly}(n),\text{poly}(n))$. Hint:

Use IP = PSPACE

Trivia: The first exercise subsumes the PCP for GNI, while the second subsumes the PCP for permanent. Both results are subsumed by $\mathsf{NEXP} = \mathsf{PCP}(\text{poly}(n),1)$.