The PCP theorem states that every NP-problem has a probabilistically checkable proof system whose randomized verifier uses 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
Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; and Szegedy, M. "Proof Verification and the Hardness of Approximation Problems." J.
ACM45, 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. ACM45, 70-122, 1998. https://doi.org/10.1145/273865.273901.
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
