The PCP Theorem, proved in full by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan and Mario Szegedy in 1998, building on earlier work including that of Laszlo Babai, Lance Fortnow and Carsten Lund, states that every decision problem in NP has a probabilistically checkable proof that a randomized verifier can check by reading only a constant number of bits, using only logarithmically many random bits, while still catching any incorrect proof with high probability. The theorem underlies the modern theory of hardness of approximation, and its original proof and Irit Dinur's later simplified 2005 proof using expander graphs each earned a Godel Prize.
Facts
StatementNP = PCP[O(log n), O(1)]: every problem in NP has a probabilistically checkable proof verifiable with logarithmic randomness and a constant number of queries. 1 Proof YearFull proof by Arora, Lund, Motwani, Sudan and Szegedy in 1998; precursor work by Arora and Safra in 1992. Sources
1. PCP theorem, Wikipedia
Formal statement
NP = PCP[O(log n), O(1)]
History
a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1998
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.