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

### MAXIMUM SATISFIABILITY OF QUADRATIC EQUATIONS OVER GF[Q]

- INSTANCE: Prime number q, set of polynomials of degree at most 2 over GF[q] in n variables. The polynomials may not contain any monomial xi2 for any i.

- SOLUTION: A subset of the polynomials such that there is a root common to all polynomials in P'.

- MEASURE: Cardinality of the subset, i.e., |P'|.

- Good News: Approximable within q2/(q-1) [227].

- Bad News: Not approximable within for any [227].

- Comment: Over the rationals or over the reals the problem is not approximable within for any [227]. For linear polynomials the problem is not approximable within for some [15].

- Garey and Johnson: Similar to AN9