__
TR01-027 | 23rd March 2001 00:00
__

#### Probabilistically Checkable Proofs The Easy Way

**Abstract:**
We present a weaker variant of the PCP Theorem that admits a

significantly easier proof. In this

variant the prover only has $n^t$ time to compute each

bit of his answer, for an arbitray but fixed constant

$t$, in contrast to

being all powerful. We show that

3SAT is accepted by a polynomial-time probabilistic verifier

that queries a constant number of bits

from a polynomially long proof string. If a boolean

formula $\phi$ of length $n$ is satisfiable, then the

verifier accepts with probability 1. If $\phi$ is not satisfiable,

then the probability that a $n^t$-bounded prover can fool the

verifier is at most 1/2. The main technical tools used in the proof

are the ``easy'' part of the PCP Theorem in which the verifier reads

a constant number of bits from an exponentially

long proof string, and the construction

of a pseudo-random generator from a one-way permutation.