PDMI TUM State University St. Petersburg
Steklov Institute St. Petersburg Technische Universität München State University St. Petersburg

Joint Advanced Student School (JASS)

Course 1: Proofs and Computers


St. Petersburg - Sunday, April 2 through Wednesday, April 12, 2006

Bernhard Vesenmayer

PCP Theorem by Gap Amplification

Abstract

The PCP Theorem provides a new classification of NP. Since the original proof by [AS98], several new proofs occured. While the first proof used highly sophisticated methods, the new approaches try to use simpler ones. In this paper the proof by [Din05] is presented. It uses the equivalence of this problem to the NP-hardness of gap-3SAT, i.e. it is this hardness that is shown. The satisfiability gap of a set of constraints is the smallest fraction of unsatisfied constraints over all assignments for the variables. Gap-3SAT is the problem of deciding whether this gap is 0 or greater than a positive constant. In this paper therefore 3SAT is polynomially reduced to gap-3SAT via gap amplification, i.e. the gap is blown up to a constant fraction.



Bernhard Vesenmayer Presentation:
PCP Theorem [PDF]
Paper:
PCP Theorem [PDF]