Positive integer n, set of linear constraints, given as an
-matrix A and an m-vector b, specifying a
A multivariate polynomial
of total degree at most 2.
The maximum value of f in the region specified by the linear constants,
Does not admit a -approximation for any constant
A -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
Note that these problems are known to be solvable in polynomial space but
are not known to be in NP.