2
$\begingroup$

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.)

$\endgroup$

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.