PCP theorem

From Wikipedia, the free encyclopedia

In computational complexity theory, the PCP theorem states that every decision problem in NP has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.

Intuitively, 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(n) 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.

Contents 1 Statement 2 PCP and hardness of approximation 3 History 4 Notes 5 References

[edit] Statement

The PCP Theorem states that

NP = PCP[O(log n), O(1)].

[edit] 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 (L_yes, L_no) is an NP-hard decision problem:

• L_yes = {Φ: all constraints in Φ are simultaneously satisfiable}
• L_no = {Φ: every assignment satisfies fewer than an α fraction of Φ's constraints},

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.

[edit] 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[poly(n), poly(n)], proved by Babai, Fortnow, and Lund in 1990. Subsequently, the method used in this work were extended by Babai, Fortnow, Levin, and Szegedy (1991), Feige, Goldwasser, Lund, Safra, and Szegedy (1991), and Arora and Safra (1992) to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1992.

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 different proof of the PCP theorem.^[1]

[edit] Notes

1. ^ See the 2005 preprint, ECCC TR05-046. The authoritative version of the paper is Dinur (2007).

[edit] References

• Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Journal of the ACM 45 (3): 501–555, doi:10.1145/278298.278306 .
• Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: A new characterization of NP", Journal of the ACM 45 (1): 70–122, doi:10.1145/273865.273901 .
• Dinur, Irit (2007), "The PCP theorem by gap amplification", Journal of the ACM 54 (3): 12, doi:10.1145/1236457.1236459 .
• Feige, Uriel; Goldwasser, Shafi; Lovász, László; Safra, Shmuel; Szegedy, Mario (1996), "Interactive proofs and the hardness of approximating cliques", Journal of the ACM 43 (2): 268–292, doi:10.1145/226643.226652 .