Query-efficient checking of proofs and improved PCP characterizations of NP
Venkatesan Guruswami · 1999
The advent of Probabilistically Checkable Proofs (PCP) established the surprising result that the validity of a proof can be checked with good accuracy by reading only a very small number of randomly selected locations of the proof. In particular, if one is willing to tolerate a small probability of error, then one need not even read the entire proof in order to check its validity! The celebrated PCP theorem [AS92, ALMSS92] shows that it is possible to encode membership in any NP language into polynomially long proofs in such a manner that a probabilistic polynomial-time verifier can read only a constant number of locations in the proof and still reject any adversarially chosen proof of a false claim of membership with 50% probability. The probability of accepting a "false proof" is called the error probability of the PCP system. The PCP theorem, in addition to being of inherent interest in proof checking, also has applications in proving hardness of approximation results for a whole ge...