__
TR04-070 | 22nd June 2004 00:00
__

#### Combinatorial and algorithmic aspects of hyperbolic polynomials

**Abstract:**
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}}$

be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients.

The support of such polynomial $p(x_1,...,x_n)$

is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 \}$ . The convex hull $CO(supp(p))$ of $supp(p)$ is called

the Newton polytope of $p$ .

We study the following decision problems , which are far-reaching generalizations of the classical perfect matching problem :

\begin{itemize}

\item

{\bf Problem 1 .} Consider a homogeneous polynomial $p(x_1,...,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,..,1) \in supp(p)$ ? }

\item

{\bf Problem 2 .} Consider a homogeneous polynomial $p(x_1,...,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,..,1) \in CO(supp(p))$ ? }

\end{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 .