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$?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIs the following problem coNP-complete?
Inputs:
Question:
Is $\forall x\in\mathbb Z: p(x)\geq k$?