THE COMPLEXITY OF APPROXIMATING A NONLINEAR PROGRAM

We consider the problem of finding the maximum of a multivariate polyn omial inside a convex polytope, We show that there is no polynomial ti me approximation algorithm for this problem, even one with a very poor guarantee, unless P = NP. We show that even when the polynomial is qu adratic (i,e, quadratic programming) there is no polynomial time appro ximation unless NP is contained in quasi-polynomial time. Our results rely on recent advances in the theory of interactive proof systems, Th ey exemplify an interesting interplay of discrete and continuous mathe matics - using a combinatorial argument to get a hardness result for a continuous optimization problem.