Probabilistically Checkable Proofs: A survey

Sanjeev Arora

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-24, 2001


The study of Probabilistically Checkable Proofs (PCPs) is an active area in theoretical computer science. At its heart is a new definition of the class NP. Classically, NP is defined as the class of decision problems such that a "Yes" answer has a short, efficiently verifiable certificate. An example is the CLIQUE problem: Given a graph G and an integer k, determine if G has a complete subgraph ("clique") on at least k nodes. Note that a "Yes" answer can be certified by exhibiting the subgraph in question. Work during the past decade gives a new definition of NP: it is the class of decision problems for which a "Yes" answer has a certificate that is probabilistically checkable by examining a constant number of bits in it. (In fact, the strongest such result shows that the certificate can be checked by examining only 3 bits in it!) Proving that this definition is equivalent to the classical definition is fairly difficult. This new definition of NP has many ramifications, one of which is that for many NP-hard problems, computing approximate solutions (solutions whose cost is within a factor 2 of the optimum, say) is no easier than computing optimum solutions. This result holds great interest for those who encounter NP-hard problems in their work. The talk will be a survey of this area, and will be self-contained.

Server START Conference Manager
Update Time 27 Jan 2001 at 12:22:07
Start Conference Manager
Conference Systems