Given the coefficients of a multivariable polynomial, how can I determine if it's bounded from below? In other words, given a polynomial $p\left(x_1,x_2,...x_n\right)$, does there exist a real number $C$ such that $p\left(x_1,x_2,...x_n\right) \ge C$?
I do not need to find the minimum value of the polynomial, I just want to know whether or not it is bounded.
Deciding whether the polynomial
$$p (x_1, x_2, \dots, x_n) - c$$
is globally nonnegative is not easy. Fortunately, deciding whether $p (x_1, x_2, \dots, x_n) - c$ can be written as a sum of squares (SOS) is easy, as the decision procedure is a semidefinite program, which is in P. However, not all globally nonnegative polynomials can be written as a sum of squares.
From one of Parrilo's papers [0], an example to clarify the above:
[0] Pablo Parrilo, Semidefinite programming relaxations for semialgebraic problems, 2001.