POLYNOMIALS OF BOUNDED TREE-WIDTH
Janos A. Makowsky, Klaus Meer · Foundations of Computational Mathematics · 2002
. 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 BlumShub -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 2 N. We are interested in three cases: (1) The evaluation of multivariate polynomials where the number of monomials is O(2 n ). Examples are the permanent or the hamiltonian polynomials. (2) For finite fields F the question whether a system of n polynomials p i (x) 2 F[x] of fixed degree d in n variables has a root in F n . (3) For infinite ordered rings (or fields) Rord , a polynomial of fixed degree d in n variables p(x) 2 Rord [x] and a finite subset A ae Ror...