Proofs, codes, and polynomial-time reducibilities

Abstract

We show how to construct proof systems for NP languages where a deterministic polynomial-time verifier can check membership, given any N(2/3)+ε bits of an N-bit witness of membership. We also provide a slightly superpolynomial time proof system where the verifier can check membership, given only N( 1/2 )+ε bits of an N-bit witness. These pursuits are motivated by the work of Gal et. al. [GHLP97]. In addition, we construct proof systems where a deterministic polynomial-time verifier can check membership, given an N-bit string that agrees with a legitimate witness on just (N/2) + N(4/5)+ε bits. Our results and framework have applications for two related areas of research in complexity theory: proof systems for NP, and the relative power of Cook reductions and Karp-Levin type reductions. Our proof techniques are based on algebraic coding theory and small sample space constructions.