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$?
$\begingroup$
$\endgroup$
-
$\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ – Yuval Filmus Nov 11 '17 at 22:16
