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
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., .
- Good News:
Approximable within
[244].
- Bad News:
Not approximable within
for any
[244].
- Comment:
Over the rationals or over the reals the problem is
not approximable within
for any
[244].
For linear polynomials the problem is not approximable within
for some
[16].
- Garey and Johnson: Similar to AN9
Viggo Kann
2000-03-20