The complexity of approximating a nonlinear program

The authors consider the problems of finding the maximum of a multivariate polynomial inside a convex polytope. They show that there is no polynomial time approximation algorithm for this problem, even one with a very poor guarantee, unless P=NP. The authors show that even when the polynomial is quadratic (i.e. quadratic programming) there is no polynomial time approximation unless NP is contained in quasi-polynomial time. The present results rely on recent advances in the theory of interactive proof systems. They exemplify an interesting interplay of discrete and continuous mathematics-using a combinatorial argument to get a hardness result for a continuous optimization problem.