期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 (logn) for {\em any} constant 1 . (Compare with the BGLR conjecture, claiming the same for
any 1 ).
Our results are in fact stronger, implying that the
constant-depend Gap-Quadratic-Solvability problem with field-size
2logn is NP-hard. We show that given a
system of quadratic polynomials each depending on a constant
number of variables ranging over a field \fld (\card\fld2logn for any constant 1 ), 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 an
O(1\card\fld) fraction.
At the same time, our proof presents a {\em 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.
