A WELL-CHARACTERIZED APPROXIMATION PROBLEM

We consider the following NP optimization problem: Given a set of poly nomials P-i(x), i = 1,...,s, of degree at most 2 over GF[p] in n varia bles, find a root common to as many as possible of the polynomials P-i (x). We prove that in the case in which the polynomials do not contain any squares as monomials, it is always possible to approximate this p roblem within a factor of p(2)/(p - 1) in polynomial time for fixed p. This follows from the stronger statement that one can, in polynomial time, find an assignment that satisfies at least (p - 1)/p(2) of the n ontrivial equations. More interestingly, we prove that approximating t he maximal number of polynomials with a common root to within a factor of p-epsilon is NP-hard. This implies that the ratio between the perf ormance of the approximation algorithm and the impossibility result is essentially p/(p - 1), which can be made arbitrarily close to 1 by ch oosing g large. We also prove that for any constant delta < 1, it is N P-hard to approximate the solution of quadratic equations over the rat ional numbers, or over the reals, within n(delta).