PCP theorem


In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.
The PCP theorem says that for some universal constant K, for every n, any mathematical proof of length n can be rewritten as a different proof of length poly that is formally verifiable with 99% accuracy by a randomized algorithm that inspects only K letters of that proof.
The PCP theorem is the cornerstone of the theory of computational hardness of approximation, which investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems. It has been described by Ingo Wegener as "the most important result in complexity theory since Cook's theorem" and by Oded Goldreich as "a culmination of a sequence of impressive works rich in innovative ideas".

Formal statement

The PCP theorem states that

PCP and hardness of approximation

An alternative formulation of the PCP theorem states that the maximum fraction of satisfiable constraints of a constraint satisfaction problem is NP-hard to approximate within some constant factor.
Formally, for some constants K and α < 1, the following promise problem is an NP-hard decision problem:
where Φ is a constraint satisfaction problem over Boolean alphabet with at most K variables per constraint.
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 P = NP. 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, NP = PCP 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 NEXP ⊆ PCP, proved by.

Etymology of the name "PCP theorem"

The notation PCPc, s 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 probably comes either from "PCP" meaning "probabilistically checkable proof", or from the notation mentioned above.

History after the first theorem in 1990

Subsequently, the methods used in this work were extended by Babai, Lance Fortnow, Levin, and Szegedy in 1991,
Feige, Goldwasser, Lund, Safra, and Szegedy, and Arora and Safra in 1992 to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 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.

Quantum analog of the PCP theorem

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 QMA ⊆ MIP*, where MIP* is a complexity class of multi-prover quantum interactive proofs systems with f-bit classical communications, and the completeness is c and the soundness is s. They also showed that the Hamiltonian version of a quantum PCP conjecture, namely a local Hamiltonian problem with constant promise gap c − s is QMA-hard, implies the games quantum PCP theorem.