PCP characterizations of NP
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Muli Safra · 1999
This paper strengthens the law-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture.Namely, we prove that witnesses for membership in any NP language can be verified with a constant nunbcr of accesses, and with an error probability exponentially small in the number of bits accessed, where this number is as high as lagan, for any constant fl < 1. (The BGLR conjecture claims the same for any p 5 1).Our results are in fact stronger, implying the Gap-Quadratic-Solvability problem to be NP-hard even if the equations are restricted to having a constant number of variables.That is, given a system of quadratic-equations over a field 3 (of size up to ZLogD"), where each equation depends on a constant number of variables, it is NP-hard to decide between the case where there is a common solution for all of the equations, and the case where any assignment satisfies no more than a & fraction of them.At the same time, ow proof presents a direct eonstmction of a low-degree-test whose error-probability is expancntially small in the number of hits accessed.Such a result was previously known only relying on recursive applications of the entire PCP theorem.