Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-027 | 23rd March 2001 00:00

Probabilistically Checkable Proofs The Easy Way


Authors: Marius Zimand
Publication: 20th April 2001 17:19
Downloads: 3514


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.

ISSN 1433-8092 | Imprint