Probabilistically checkable proofs

$\mathbf{PCP}[r(n),q(n)]$ is the class of languages $L$ with a probabilistic polynomial-time oracle verifier $V$ that, on input $x\in \{0,1{\}}^n$ and oracle access to a proof $\pi$, uses $O(r(n))$ random bits and makes $O(q(n))$ queries to $\pi$, such that if $x\in L$ then $\mathrm{Pr}[V^{\pi }(x)=1]=1$ for some $\pi$, and if $x\notin L$ then $\mathrm{Pr}[V^{\pi }(x)=1]\le 1/2$ for every $\pi$ — AS92. PCP denotes $\mathbf{PCP}[\log n,1]$, logarithmic randomness and a constant number of queries.

Notable problems

• Every language in $\mathbf{NP}$, by the PCP theorem: PCP = NP — ALM+92.

Known relationships

• $\mathbf{PCP}[\log n,1]=\mathbf{NP}$ — ALM+92, building on AS92.
• With polynomial randomness and polynomially many queries the verifier is equivalent to a multi-prover interactive proof — FRS88 — so $\mathbf{PCP}[\mathrm{poly}(n),\mathrm{poly}(n)]=\mathbf{NEXP}$ — BFL90.
• A PCP is a one-round interactive oracle proof — BCS16.

Participates in

Builds on Probabilistically checkable proofs

• PCP = NP

Used via Probabilistically checkable proofs

• CRHF ⇒ Succinct arguments for NP (Kilian)
• ROM ⇒ SNARK (Micali’s CS proofs)