The PCP theorem states that every NP-problem has a probabilistically checkable proof system whose randomized verifier uses upper
bound on the probability of accepting an incorrect proof. In complexity notation,
the theorem is
It is a fundamental source of results showing that approximation
problems are NP-hard .
See also Closest Vector Problem ,
NP-Hard Problem ,
NP-Problem ,
Proof ,
Projection
Games Conjecture ,
Satisfiability Problem
Explore with Wolfram|Alpha
References Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; and Szegedy, M. "Proof Verification and the Hardness of Approximation Problems." J.
ACM 45 , 501-555, 1998. https://doi.org/10.1145/278298.278306 . Arora,
S. and Safra, S. "Probabilistic Checking of Proofs: A New Characterization of
NP." J. ACM 45 , 70-122, 1998. https://doi.org/10.1145/273865.273901 .
Cite this as:
Weisstein, Eric W. "PCP Theorem." From
MathWorld https://mathworld.wolfram.com/PCPTheorem.html
Subject classifications
random bits and reads only 
bits of the proof, with a constant upper
bound on the probability of accepting an incorrect proof. In complexity notation,
the theorem is
