A well-characterized approximation problem (Q688442): Difference between revisions

We consider the following NP optimization problem: Given a set of polynomials \(P_ i(x)\), \(i=1,\ldots,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_ 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 problem 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 nontrivial equations. More interestingly, we prove that approximating the maximal number of polynomials with a common root to within a factor of \(p-\varepsilon\) 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 \(\delta<1\), it is NP-hard to approximate the solution of quadratic equations over the rational numbers, or over the reals, within \(n^ \delta\).