8th Estonian Winter School in Computer Science (EWSCS)
VIII Eesti Arvutiteaduse Talvekool (EATTK)
Palmse, Estonia
March 2 - 7, 2003
Johan Håstad
NADA
Kungl Tekniska Högskolan, Stockholm
Probabilistically Checkable Proofs and Inapproximability
Abstract
A traditional NP-proof of a statement is verified by a polynomial time deterministic verifier that always accepts a correct proof and never accepts a proof of an incorrect statement. The verifier typically would read the entire proof.
A Probabilistically Checkable Proof (or simply PCP) is verified by a polynomial time probabilistic verifier that only reads a very small part of the proof. The celebrated PCP-theorem says that any NP-statement admits a PCP where a correct proof is always accepted and where the verifier only reads a number of bits that is independent of the size of the statement being proved. A proof of an incorrect statement is accepted with probability at most a half.
Apart from being a mathematically appealing concept, PCPs (with proper parameters) are extremely useful for proving inapproximability results for NP-hard optimization problems.
The aim of the first part of the course is to give an outline and part of the proof of the PCP-theorem. The second part of the course will give applications to inapproximability of some basic NP-hard optimization problems.
Course materials
M. Sudan. Probabilistically checkable proofs. Course notes for Graduate Summer School within Inst. for Adv. Study/Park City Math. Inst. 2000 Summer Session on Computational Complexity Theory (Princeton, NJ, July/Aug. 2000). [ps]
J. Håstad. On linear equations and satisfiability. Notes (based on the paper Some optimal inapproximability results), 2003. [ps]