Combinatorial and algorithmic aspects of hyperbolic polynomials

Let $p(x_1,…,x_n) =\sum_{(r_1,…,r_n) \in I_{n,n}} a_{(r_1,…,r_n)} \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$behomogeneouspolynomialofdegree$n$in$n$ real variables with integer nonnegative coefficients. The support of such polynomial $p(x_1,\mathrm{.}\mathrm{.}\mathrm{.},x_n)$ is defined as $supp(p) = {(r_1,…,r_n) \in I_{n,n} : a_{(r_1,…,r_n)} \neq 0 }$\mathrm{.}Theconvexhull$CO(supp(p))$of$supp(p)$iscalledtheNewtonpolytopeof$p$ . We study the following decision problems, which are far-reaching generalizations of the classical perfect matching problem : {itemize} {\bf Problem 1 .} Consider a homogeneous polynomial $p(x_1,\mathrm{.}\mathrm{.}\mathrm{.},x_n)$ of degree $n$ in $n$ real variables with nonnegative integer coefficients given as a black box (oracle) . {\it Is it true that $(1,1,\mathrm{.}\mathrm{.},1)\in supp(p)$ ?} {\bf Problem 2 .} Consider a homogeneous polynomial $p(x_1,\mathrm{.}\mathrm{.}\mathrm{.},x_n)$ of degree $n$ in $n$ real variables with nonnegative integer coefficients given as a black box (oracle) . {\it Is it true that $(1,1,\mathrm{.}\mathrm{.},1)\in CO(supp(p))$ ?} {itemize} We prove that for hyperbolic polynomials these two problems are equivalent and can be solved by deterministic polynomial-time oracle algorithms . This result is based on a “hyperbolic” generalization of Rado theorem .