  We prove that unless P=NP, there exists no polynomial time (or even
pseudo-polynomial time) algorithm that can test whether the optimal value of a
nonlinear optimization problem where the objective and constraints are given by
low-degree polynomials is attained. If the degrees of these polynomials are
fixed, our results along with previously-known "Frank-Wolfe type" theorems
imply that exactly one of two cases can occur: either the optimal value is
attained on every instance, or it is strongly NP-hard to distinguish attainment
from non-attainment. We also show that testing for some well-known sufficient
conditions for attainment of the optimal value, such as coercivity of the
objective function and closedness and boundedness of the feasible set, is
strongly NP-hard. As a byproduct, our proofs imply that testing the Archimedean
property of a quadratic module is strongly NP-hard, a property that is of
independent interest to the convergence of the Lasserre hierarchy. Finally, we
give semidefinite programming (SDP)-based sufficient conditions for attainment
of the optimal value, in particular a new characterization of coercive
polynomials that lends itself to an SDP hierarchy.
