MAXIMUM SATISFIABILITY OF QUADRATIC EQUATIONS OVER GF[Q]

Next: Games and Puzzles Up: Solvability of Equations Previous: Solvability of Equations Index

INSTANCE: Prime number q, set $P=\{p_1(x), p_2(x),\ldots,p_m(x)\}$ of polynomials of degree at most 2 over GF[q] in n variables. The polynomials may not contain any monomial ${x_i}^2$ for any i.
SOLUTION: A subset $P'\subseteq P$ of the polynomials such that there is a root common to all polynomials in P'.
MEASURE: Cardinality of the subset, i.e., $\vert P'\vert$ .
Good News: Approximable within [244].
Bad News: Not approximable within $q-\varepsilon$ for any $\varepsilon$ [244].
Comment: Over the rationals or over the reals the problem is not approximable within $n^{1-\varepsilon }$ for any $\varepsilon >0$ [244]. For linear polynomials the problem is not approximable within $q^\varepsilon$ for some $\varepsilon >0$ [16].
Garey and Johnson: Similar to AN9

Viggo Kann
2000-03-20