# Global Minimum of Multivariate Polynomial is coNP-complete? [closed]

Is the following problem coNP-complete?

Inputs:

• $p=$ a possibly non-convex multivariate polynomial over $\mathbb Z$
• $k\in \mathbb Z$, an integer

Question:

Is $\forall x\in\mathbb Z: p(x)\geq k$?

• What do you think? What have you tried, and where did you get stuck? Nov 11 '17 at 22:16