| |
| | ECCC Report TR04-070 and related Papers (Site not responding. Last check: 2007-10-09) |
 | | 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 }$. |
 | | 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 fl box (oracle). |
| eccc.hpi-web.de /eccc-reports/2004/TR04-070/index.html (214 words) |
|