PCP theorem
The PCP theorem is a sentence from complexity theory , a branch of theoretical computer science .
statement
The PCP theorem is based on the concept of the randomly verifiable proof of a mathematical theorem (probabilistic checkable proof, PCP), which in turn goes back to the concept of interactive proof systems introduced by Shafi Goldwasser , Charles Rackoff and Silvio Micali in the early 1980s . The idea behind this was that the verification of proofs of mathematical theorems is usually much easier than the proof itself (which the authors had a cryptographic background).
A proof of an assertion A consists of a sequence of rules of derivation applied to the axioms of the formal system. This is formalized in the form of an algorithm, called a verifier, which has an assertion A and the "evidence" E as input and calculates whether E is a proof of A. PCP assumes that a random number generator is available to verify evidence and that direct access ( oracle ) to any bits at any point in the proof. The PCP then includes the minimum probability with which a proof will be accepted (it should be 1, completeness ) and the minimum probability with which a false proof will be rejected (should be 1/2, soundness ). The PCP theorem then makes quantitative statements about the size of the components of the verification algorithm used, depending on the size of the evidence (length n bits): the number of bits to be queried is limited by a universal constant K, regardless of n, and the number of bits used of the random number generator is of the order of log (n).
PCP theorem: Every decision problem in the NP class can be solved by a PCP proof with constant complexity of the questions and logarithmic random complexity:
- NP = PCP (O (log n ), O (1))
history
The theorem is based on a long series of works in which the PCP concept was developed. In the 1990s, Sanjeev Arora , Shmuel Safra , László Babai , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy , Lance Fortnow , Shafi Goldwasser , Uriel Feige and László Lovász were involved . In 2001 Arora, Goldwasser, Feige, Lund, Motwani, Safra, Lovasz, Sudan and Szegedy received the Gödel Prize for proof . In 1996, Feige and co-authors established an equivalence of the theorem for the non-approximability of certain optimization problems. The evidence was then published by Arora, Safra, and others in 1998.
In 2005 Irit Dinur succeeded in a radically simplified new proof of the PCP theorem. Dinur also started from the solution of an optimization problem (constraint satisfaction) in order to prove the equivalent PCP problem.
literature
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof verification and the hardness of approximation problems. In: Journal of the ACM. Vol. 45, 1998, pp. 501-555 (proof of the PCP theorem)
- Sanjeev Arora, Shmuel Safra: Probabilistic checking of proofs: a new characterization of NP. In: Journal of the ACM. Vol. 45, 1998, pp. 70–122 (proof of the theorem)
- Sanjeev Arora: How NP got a new definition: a survey of probabilistically checkable proofs , ICM Beijing 2002, Arxiv
- Laszlo Babai, Lance Fortnow, Leonid Levin, Carsten Lund: Non deterministic exponential time has two-prover interactive proofs. In: Proc. of the 23rd ACM Symposium on the theory of computing. 1991
- Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, Mario Szegedy: Interactive proofs and the hardness of approximating cliques. In: Journal of the ACM. Volume 43, 1996, pp. 268-292.
- Irit Dinur: The PCP theorem by gap amplification. Technical Report 2005 and Journal of the ACM, Volume 54, 2007, pp. 1-12, online
- Jaikumar Radhakrishnan, Madhu Sudan: On Dinur's Proof of the PCP Theorem. In: Bulletin AMS. Vol. 44, 2007, pp. 19-61, online