PCP-Theorem

The PCP theorem is a set of complexity theory, a branch of theoretical computer science.

Statement

The PCP theorem is based on the concept of random verifiable proof of a mathematical theorem ( probabilistic checkable proof, PCP), which goes back again to the concept of Interactive Proof Systems, which were introduced in the early 1980s by Shafi Goldwasser, Charles Rackoff and Silvio Micali. The idea was that the verification of proofs of mathematical sentences usually much simpler than the proof itself (which the authors had a cryptographic background).

A proof of a proposition A is a sequence of derivation rules applied to the axioms of the formal system. This is called in the form of an algorithm, verifier, formalized, and has calculated that e is a proof of A is an assertion A and the "evidence " E as input. PCP assumes that verification of a proof is a random number generator is available, and direct access ( oracle ) on arbitrary bits at any point of the proof. In the PCP then goes to the minimum probability with which a proof is accepted (it should be 1, Completeness ) and the minimum probability of a false proof is rejected ( should be 1 /2, Soundness ). The PCP theorem then makes quantitative statements about the size of the components used in the verification algorithm as a function of the size of the proof (length n bits): the number of to erfragenden bits is bounded independently of n by a universal constant K and the number of bits used 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 issues and logarithmic random complexity:

History

The theorem is based on a long series of works in which the PCP concept was developed. Were involved in the 1990s Sanjeev Arora, Shmuel Safra, Laszlo Babai, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy, Lance Fortnow, Shafi Goldwasser, Uriel Feige, Laszlo Lovasz. 1991 received Arora, Goldwasser, fig, Lund, Motwani, Safra, Lovasz, Sudan and Szegedy for the proof of the Gödel Prize. Fig and co- authors reported in 1996 an equivalence of the theorem to the non- approximability of certain optimization problems ago. The evidence was then published by Arora, Safra and other 1998.

Irit Dinur 2005 achieved a radically simplified new proof of the PCP theorem. Dinur also started from the solution of an optimization problem ( constraint satisfaction ) to prove the equivalent PCP problem.