Description of Johan Hastad's lectures at the
Fall school (Sept.'03)

PCPs and Inapproximability

A traditional NP-proof of a statement is verfied by a polynomial time determinstic 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 verfied 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 main part of the lectures will be devoted to outlining the proof of the PCP-theorem and towards the end we will briefly discuss applications to inapproximability of some basic NP-hard optimization problems.