PCP theorem

PCP and hardness of approximation

An alternative formulation of the PCP theorem states that the maximum fraction of satisfiable constraints of a certain constraint satisfaction problem is NP-hard to approximate within some constant factor.

Formally, for some constants ${\displaystyle q}$ and ${\displaystyle \alpha <1}$, the following promise problem ${\displaystyle (L_{\mathrm{y}\mathrm{e}\mathrm{s}},L_{\mathrm{n}\mathrm{o}})}$ is an NP-hard decision problem:

• ${\displaystyle L_{\mathrm{y}\mathrm{e}\mathrm{s}}=\{\mathrm{\Phi }:}$ all constraints in ${\displaystyle \mathrm{\Phi }}$ are simultaneously satisfiable${\displaystyle \}}$
• ${\displaystyle L_{\mathrm{n}\mathrm{o}}=\{\mathrm{\Phi }:}$ every assignment satisfies fewer than an ${\displaystyle \alpha }$ fraction of ${\displaystyle \mathrm{\Phi }}$'s constraints${\displaystyle \}}$

where ${\displaystyle \mathrm{\Phi }}$ is a constraint satisfaction problem (CSP) over a Boolean alphabet with at most ${\displaystyle q}$ variables per constraint.

The connection to the class ${\displaystyle \mathsf{P}\mathsf{C}\mathsf{P}}$ mentioned above can be seen by noticing that checking a constant number of bits ${\displaystyle q}$ in a proof can be seen as evaluating a constraint in ${\displaystyle q}$ Boolean variables on those bits of the proof. Since the verification algorithm uses ${\displaystyle O(\log n)}$ bits of randomness, it can be represented as a CSP as described above with ${\displaystyle \mathrm{poly}(n)}$ constraints. The first formulation of the PCP theorem then guarantees the promise condition with ${\displaystyle \alpha =\frac{1}{2}}$: if the NP problem's answer is yes, then every constraint (which corresponds to a particular value for the random bits) has a satisfying assignment (an acceptable proof); otherwise, any proof should be rejected with probability at least ${\displaystyle \frac{1}{2}}$, which means any assignment must satisfy fewer than ${\displaystyle \frac{1}{2}}$ of the constraints (which means it will be accepted with probability lower than ${\displaystyle \frac{1}{2}}$). Therefore, an algorithm for the promise problem would be able to solve the underlying NP problem, and hence the promise problem must be NP-hard.

As a consequence of this theorem, it can be shown that the solutions to many natural optimization problems including maximum boolean formula satisfiability, maximum independent set in graphs, and the shortest vector problem for lattices cannot be approximated efficiently unless ${\displaystyle \mathsf{P}=\mathsf{N}\mathsf{P}}$. This can be done by reducing the problem of approximating a solution to such problems to a promise problem of the above form. These results are sometimes also called PCP theorems because they can be viewed as probabilistically checkable proofs for NP with some additional structure.

Proof

A proof of a weaker result, ⁠${\displaystyle \mathsf{N}\mathsf{P}\subseteq \mathsf{P}\mathsf{C}\mathsf{P}[n^3,1]}$⁠ is given in one of the lectures of Dexter Kozen.

History

The PCP theorem is the culmination of a long line of work on interactive proofs and probabilistically checkable proofs. The first theorem relating standard proofs and probabilistically checkable proofs is the statement that ${\displaystyle \mathsf{N}\mathsf{E}\mathsf{X}\mathsf{P}\subseteq \mathsf{P}\mathsf{C}\mathsf{P}[\mathrm{poly}(n),\mathrm{poly}(n)]}$, proved by Babai, Fortnow & Lund (1990).

Origin of the initials

The notation ${\displaystyle {\mathsf{P}\mathsf{C}\mathsf{P}}_{c(n),s(n)}[r(n),q(n)]}$ is explained at probabilistically checkable proof. The notation is that of a function that returns a certain complexity class. See the explanation mentioned above.

The name of this theorem (the "PCP theorem") probably comes either from "PCP" meaning "probabilistically checkable proof", or from the notation mentioned above (or both).

First theorem [in 1990]

Subsequently, the methods used in this work were extended by Babai, Lance Fortnow, Levin, and Szegedy in 1991 (Babai et al. 1991), Feige, Goldwasser, Lund, Safra, and Szegedy (1991), and Arora and Safra in 1992 (Arora & Safra 1992) to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1998 (Arora et al. 1998).

The 2001 Gödel Prize was awarded to Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy for work on the PCP theorem and its connection to hardness of approximation.

In 2005 Irit Dinur discovered a significantly simpler proof of the PCP theorem, using expander graphs. She received the 2019 Gödel Prize for this.

In 2025 the PCP theorem was proven to hold even when limited to perfectly zero knowledge proofs.

Quantum analogs

Nonlocal games version

A version of the PCP theorem for quantum nonlocal games would state that it is computationally hard to approximate the quantum value of a quantum nonlocal game. In 2012, Thomas Vidick and Tsuyoshi Ito published a result that showed a "strong limitation on the ability of entangled provers to collude in a multiplayer game". This could be a step toward proving the quantum analogue of the PCP theorem, since when the result was reported in the media, professor Dorit Aharonov called it "the quantum analogue of an earlier paper on multiprover interactive proofs" that "basically led to the PCP theorem".

In 2018, Thomas Vidick and Anand Natarajan proved a games variant of quantum PCP theorem under randomized reduction. It states that ${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}\subseteq {\mathsf{M}\mathsf{I}\mathsf{P}}^{\ast }[\log n,1,\frac{1}{2}]}$, where ${\displaystyle {\mathsf{M}\mathsf{I}\mathsf{P}}^{\ast }[f(n),c,s]}$ is a complexity class of multi-prover quantum interactive proofs systems with ${\displaystyle f(n)}$-bit classical communications, and the completeness is ${\displaystyle c}$ and the soundness is ${\displaystyle s}$.

Hamiltonian version

A version of the PCP theorem for quantum local Hamiltonians would state that it is computationally hard to approximate the ground energy of a quantum local Hamiltonian. The work of Natarajan and Vidick also showed that a quantum Hamiltonian version of the PCP theorem, namely the existence of local Hamiltonian problem with constant promise gap ${\displaystyle c-s}$ which are QMA-hard, implies a quantum nonlocal games version of the PCP theorem.

The NLTS conjecture was an unresolved obstacle and precursor to a quantum Hamiltonian analog of the PCP theorem. The conjecture was proven in 2022 by Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe using a construction of a Hamiltonian based on quantum CSS codes. However, the ground states of such Hamiltonians are given explicitly by the code states of the corresponding CSS code, and thus are not computationally hard enough for a general proof of a quantum PCP theorem.