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 of length n is satisfiable, then the verifier accepts with probability 1. If 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.
展开▼
