|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-00-061
Polynomials
of Bounded Tree-Width
J.A. Makowsky, K. Meer
Abstract
We introduce a new sparsity conditions on multivariate polynomials
in $n$ variables (over some ring $R$) and show that under this condition
many otherwise intractable computational problems involving these
polynomials become solvable in polynomial (even linear) time in $n$
(in the $BSS$-model over $R$). To define our sparsity condition we
associate with these polynomials a hypergraph and study classes of
polynomials where this hypergraph has tree width at most $k$ for some
fixed $k \in \mathbb{N}$. We are interested in three cases:
(1) The evaluation of multivariate polynomials where the number of
monomials is $O(2^n)$.
(2) The question whether a system of $n$ polynomials $p_i(\bar{x})
\in R[\bar{x}]$ of fixed degree $d$ in $n$ variables has a root in
$R^n$.
(3) For infinite ordered rings $R_{ord}$, a polynomial of fixed degree
$d$ in $n$ variables $p(\bar{x}) \in R_{ord}[\bar{x}]$ and a finite
subset $A \subset R_{ord}$ we want to know whether $p(\bar{a}) > 0$
for all $\bar{a} \in R_{ord}^n$. Our method uses graph theoretic and
model theoretic tools developed in the last 15 years and applies them
to the algebraic setting.
This work is an extension of work by B. Courcelle, J.A. Makowsky and
U. Rotics.
.
Download
Compressed Postscript
|