Next: Games and Puzzles
Up: Solvability of Equations
Previous: Solvability of Equations
  Index
- 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
Viggo Kann
1999-04-22