A WELL-CHARACTERIZED APPROXIMATION PROBLEM

作     者：HASTAD, J PHILLIPS, S SAFRA, S 

作者机构：STANFORD UNIVDEPT COMP SCISTANFORDCA 94305 IBM CORPALMADEN RES CTRSAN JOSECA 95120 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1993年第47卷第6期

页      面：301-305页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Mitsubishi OTL National Science Foundation, NSF 

主　　题：COMPUTATIONAL COMPLEXITY THEORY OF COMPUTATION APPROXIMATION ALGORITHM 

摘      要：We consider the following NP optimization problem: Given a set of polynomials P-i(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 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-epsilon 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 g 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).