1
$\begingroup$

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$?

Improve this question
$\endgroup$
1
  • $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$
    – Yuval Filmus
    Nov 11 '17 at 22:16