The PCP theorem states that every NP-problem has a probabilistically checkable proof system with a randomized polynomial
time verifier. On an input of length 
, the verifier uses 
random bits and reads only 
bits of the proof. For a yes-instance, some proof is accepted
with probability 1; for a no-instance, every proof is accepted with probability at
most 
. In complexity notation, the theorem
is
 |
It is a fundamental source of results showing that approximation problems are NP-hard.
