6
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ Did you see chapter 11 (PCP theorem and hardness of approximation: An introduction) in Arora-Barak? It contains simple PCPs for graph non-isomorphism, permanent and a proof of $\mathsf{NP} \subseteq \mathsf{PCP}(n^3,1)$ (which is far easier than $\mathsf{PCP}(\log n,1)$). $\endgroup$ – sdcvvc Jul 12 '13 at 11:27
  • $\begingroup$ See this reading group. $\endgroup$ – Kaveh Jul 12 '13 at 12:52
  • $\begingroup$ For the permanent, you can check this writeup. $\endgroup$ – Yuval Filmus Jul 13 '13 at 21:15
8
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ I'd appreciate a comment about the footnote. Did I miss something, can we gloss over this with good conscience or is it a serious bug ? $\endgroup$ – Raphael Jul 16 '13 at 8:25
  • $\begingroup$ You can use rejection sampling to sample a random permutation with arbitrarily small constant failure probability using $O(n\log n)$ bits; in case of failure, you can choose the identity permutation. This way all three properties are satisfied. (You may have to repeat the test to get a probability of $1/2$ in the final property.) $\endgroup$ – Yuval Filmus Jul 16 '13 at 19:22
2
$\begingroup$

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

$\endgroup$

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.