The Probabilistically Checkable Proofs Theorem

Colin Sandon , Princeton University
Fine Hall 314

The class NP consists of types of problems for which there is always a reasonably short proof that the answer is yes when it is. While it intuitively seems like one would have to read the entirety of an alleged proof to determine whether or not it is valid, this is actually false, provided one is willing to accept a small probability of accepting a “proof” of a false statement. In fact, one only needs to read a constant number of bits to differentiate with high probability between true proofs and claimed proofs of false statements. This can be used to show that unless P=NP, there are certain problems where not only is the solution hard to calculate, it is even hard to approximate.