A well-characterized approximation problem

Abstract

We consider the following NP optimization problem: Given a set of polynomials Pi(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 Pi(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 problem within a factor of p2/(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)/p2 of the nontrivial equations. More interestingly, we prove that approximating the maximal number of polynomials with a common root to within a factor of p - ε is NP-hard. This implies that the ratio between the performance of the approximation algorithm and the impossibility result is essentially p /(p-1), which can be made arbitrarily close to 1 by choosing p large. We also prove that for any constant δ < 1, it is NP-hard to approximate the solution of quadratic equations over the rational numbers, or over the reals, within nδ. © 1993.