Consider $n$ variables $x_1, \cdots, x_n$ and $f=\sum a_i x_1^{d_{i1}}\cdots x_n^{d_{in}}$ such that for each $i$, $d_{i1}+\cdots+d_{in}=d$ for some fixed $d$ and $a_i\geq 0$.

I am interested in the following question :- given $f$ and $\theta$ decide whether there exist $x_i$ such that $\sum_{i=1}^n x_i=1$ and $x_i\geq 0$, $f\geq \theta$.

Is this problem $NP_R$-hard? (I am referring the Blum–Shub–Smale model.)


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.