##
The complexity of approximating a nonlinear program

** Authors:** Mihir Bellare and Phillip Rogaway

** Reference:** *
Journal of Mathematical Programming B*, Vol. 69, No. 3, pp. 429-441,
September 1995. (Earlier version in Complexity of Numerical
Optimization, P. M. Pardalos, ed., World Scientific, 1993.)

** Abstract: **
We consider the problem of finding the maximum of a multivariate polynomial
inside a convex polytope. We show that there is no good polynomial time
approximation algorithm for this problem unless P=NP. We
show that even quadratic programming (the case where the polynomial is
quadratic) has no good polynomial time approximation algorithm unless
NP is contained in quasi-polynomial time.
Our results rely on recent advances in the theory of interactive proof systems.
They exemplify an unusual interplay of discrete and continuous
mathematics - using a combinatorial argument to get a hardness result for a
continuous optimization problem.

Full version available in
PDF or PostScript .

Rogaway's home page.