Electronic Colloquium on Computational Complexity, Report No. 66 (1998) PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

This paper strengthens the low-error PCP characterization of NP, coming closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for membership in any NP language can be verified with a constant number of accesses, and with an error probability exponentially small in the number of bits accessed, as long as this number is at most for any constant. (Compare with the BGLR conjecture, claiming the same for any). Our results are in fact stronger, implying that the constant-depend Gap-Quadratic-Solvability problem with! field-size is NP-hard. We show that given a system of quadratic polynomials each depending on a constant number of variables ranging over a " ( # "$#&%' ( ! field for any) * constant), it is NP-hard to decide between the case where there is a common root for all of the polynomials, and the case where every assignment zeros at most +,.- / 01 / an fraction. At the same time, our proof presents a direct construction of a low-degree-test whose error-probability is exponentially small in the number of bits accessed. Such a result was previously known only by relying on recursive applications of the PCP theorem