Name
Abstract | ||
|---|---|---|
We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree- width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of partic- ular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width. We show that the class of polynomials arising from families of poly- nomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying argu- ments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree- width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P 6⊆ F P/poly. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-92248-3_23 | Workshop on Graph-Theoretic Concepts in Computer Science |
Keywords | Field | DocType |
general permanent polynomial,bounded tree-width matrix,expressive power,bounded tree-width,cnf polynomial,bounded tree,related cnf polynomial,arithmetic formula,cnf formula,previous paper,bounded clique-width,cnf formulas,communication complexity,conjunctive normal form | Discrete mathematics,Combinatorics,Koornwinder polynomials,Polynomial,Macdonald polynomials,Jacobi polynomials,Conjunctive normal form,Monomial,Mathematics,Difference polynomials,Bounded function | Conference |
Volume | ISSN | Citations |
5344 | 0302-9743 | 5 |
PageRank | References | Authors |
0.50 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pascal Koiran | 1 | 919 | 113.85 |
| Klaus Meer | 2 | 28 | 4.91 |
| José Antonio Martín H. | 3 | 140 | 14.43 |