- 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