Polynomials of Bounded Tree Width (Extended Abstract)

J. A. Makowsky () and K. Meer ()
Additional contact information
J. A. Makowsky: Technion-Israel Institute of Technology, Department of Computer Science
K. Meer: Fakultät für Informatik

A chapter in Formal Power Series and Algebraic Combinatorics, 2000, pp 692-703 from Springer

Abstract: 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 ∈ ℕ. 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 ( $$\overline x $$ ) ∈ R[ $$\overline 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 ( $$\overline x $$ ) ∈ R ord [ $$\overline x $$ ] and a finite subset A ⊂ R ord we want to know whether p(ā)

Keywords: Constraint Satisfaction; Order Logic; Graph Transformation; Polynomial System; Algebraic Setting (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-04166-6_68

Ordering information: This item can be ordered from
http://www.springer.com/9783662041666

DOI: 10.1007/978-3-662-04166-6_68

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().