Monday, March 19, 2001

11:00 AM

CSB 209

Marius Zimand

Towson University

Probabilistically Checkable Proofs the Easy Way

The PCP Theorem is one of the deepest and most important theorems in complexity theory. It asserts that solutions for NP problems can be checked in polynomial time by reading only a constant number of their bits, and no prover can fool the verifier into accepting a false solution except with very small probability. The proof is long, difficult, and technical.

I will present a weaker variant of the PCP Theorem that admits a much easier proof. This is important for pedagogical reasons and, perhaps, also for practical applications of probabilistically checkable proofs. In this variant, the prover has $n^t$ time to compute each bit of her or his proof, in contrast to being all-powerful in the full PCP Theorem. All the other parameters remain the same. I show that 3SAT is accepted by a polynomial-time probabilistic verifier that reads only a constant number of bits from a polynomially long proof. If a boolean formula \phi is satisfiable, then the verifier accepts with probability 1. If \phi is not satisfiable then the probability that an n^t bounded prover can fool the verifier is at most 1/2. The proof is simple, using an easy part from the proof of the full PCP Theorem and some standard cryptographic constructions.