It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$.

Input: a list $P$ of triplets $(a,s,t)$ where $s$ and $t$ are nonnegative integers.
Output: is there an $x\in \mathbb{R}$ such that $$p(x) =\sum_{(a,s,t) \in P} a x^s(1-x)^t \geq 0?$$

Is this problem $\mathsf{NP}_\mathbb{R}$-hard?

  • 1
    $\begingroup$ The question is essentially if the given $-p(x)$ is not always positive so Positivstellensatz might be related. $\endgroup$ – Kaveh Jun 30 '15 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.