Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Satisfying Degree-d Equations over GF[2] n
verfasst von : Johan Håstad
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the problem where we are given a system of polynomial equations defined by multivariate polynomials over
GF
[2] of fixed constant degree
d
> 1 and the aim is to satisfy the maximal number of equations. A random assignment approximates this problem within a factor 2
−
d
and we prove that for any
ε
> 0, it is NP-hard to obtain a ratio 2
−
d
+
ε
. When considering instances that are perfectly satisfiable we give a probabilistic polynomial time algorithm that, with high probability, satisfies a fraction 2
1 −
d
− 2
1 − 2
d
and we prove that it is NP-hard to do better by an arbitrarily small constant. The hardness results are proved in the form of inapproximability results of Max-CSPs where the predicate in question has the desired form and we give some immediate results on approximation resistance of some predicates.