PCP = NP

Equivalence · ALM+92

Statement

$\mathbf{PCP}[O(\log n),O(1)]=\mathbf{NP}$: every $L\in \mathbf{NP}$ has a probabilistic polynomial-time verifier $V$ that, on input $x\in \{0,1{\}}^n$ and oracle access to a proof string $\pi$, uses $O(\log n)$ random bits, reads a constant number of bits of $\pi$, accepts with probability $1$ for some $\pi$ when $x\in L$, and accepts every $\pi$ with probability at most $1/2$ when $x\notin L$ (PCP) — ALM+92. ALM+92 build on AS92, who characterize $\mathbf{NP}$ as the languages whose membership proofs a polynomial-time verifier checks using $O(\log n)$ random bits and a sub-logarithmic number of queries, and who introduce the recursive composition of verifiers both papers use — AS92. The converse inclusion $\mathbf{PCP}[O(\log n),O(1)]\subseteq \mathbf{NP}$ is standard.

Sketch

For $\mathbf{PCP}[O(\log n),O(1)]\subseteq \mathbf{NP}$: over all $2^{O(\log n)}=\mathrm{poly}(n)$ coin strings the verifier reads at most $\mathrm{poly}(n)$ positions of $\pi$, so an $\mathbf{NP}$ machine guesses those bits and runs $V$ on every coin string, accepting iff all runs accept — standard.

Notes

• Only $2^{O(\log n)}\cdot O(1)$ positions of $\pi$ can be addressed, so the proof has length $\mathrm{poly}(n)$ — standard. Running the verifier $k$ times with independent coins gives soundness error $2^{-k}$ with $O(k)$ queries and $O(k\log n)$ random bits — standard.
• The multi-prover analogue at exponential scale is MIP = NEXP — BFL90.