ALCOMFT-TR-01-36

J.A. Makowsky and K. Meer
Polynomials of bounded tree-width
Århus. Work package 4. April 2001.

Abstract: We introduce a new sparsity conditions, the tree-width, 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 (in some cases even linear) time in n in the Blum-Shub-Smale-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 N.

We are interested in three cases:

(1) The evaluation of multivariate polynomials where the number of monomials is O(2ⁿ). Examples are the permanent or the hamiltonian polynomials.

(2) For finite fields F the question whether a system of n polynomials p_i(\barx) \in F[\barx] of fixed degree d in n variables has a root in Fⁿ.

(3) For infinite ordered rings (or fields) R_ord, a polynomial of fixed degree d in n variables p(\barx) \in R_ord[\barx] and a finite subset A \subset R_ord we want to know whether p(\bara) > 0 for all \bara \in R_ordⁿ.

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 and by Arneborg, Lagergren, and Seese.

Postscript file: ALCOMFT-TR-01-36.ps.gz (175 kb).