A well-characterized approximation problem (Q688442): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Simple Constructions of Almost k-wise Independent Random Variables / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4230322 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4230321 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient probabilistically checkable proofs and applications to approximations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2743964 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the hardness of approximating minimization problems / rank | |||
Normal rank |
Revision as of 10:36, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A well-characterized approximation problem |
scientific article |
Statements
A well-characterized approximation problem (English)
0 references
13 March 1994
0 references
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\).
0 references
NP-hard
0 references
approximation algorithm
0 references