-matrix
A
and an
m
-vector
b
, specifying a
region
by
.
of total degree at most 2.
.
-approximation for any constant
[
42
].
-approximation algorithm finds a solution that differs from the
optimal solution by at most the value
.
Variation in which we look for a polynomial
f
of any degree
does not admit a
-approximation for
for some
[
42
].
Note that these problems are known to be solvable in polynomial space but
are not known to be in NP.
Viggo Kann