About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Information Processing Letters
Paper
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.