Soft x-ray diffraction of striated muscle
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
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.
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006
Hendrik F. Hamann
InterPACK 2013
Rajeev Gupta, Shourya Roy, et al.
ICAC 2006