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 arbitrary 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.
展开▼
