A well-characterized approximation problem
Johan Håstad, Steven D. Phillips, Muli Safra · 2002
The authors consider the following NP optimization problem: given a set of polynomials P/sub i/(x), i=1. . .s of degree at most 2 over GF(p) in n variables, find a root common to as many as possible of the polynomials P/sub i/(x). They prove that in the case when the polynomials do not contain any squares as monomials, it is always possible to approximate this problem within a factor of /sup p2///sub p-1/ in polynomial time. This follows from the stronger statement that one can, in polynomial time, find an assignment that satisfies at least /sup p-1///sub p2/ of the nontrivial equations. More interestingly, they prove that approximating the maximal number of polynomials with a common root to within a factor of p- in is NP-hard. They also prove that for any constant delta>