Academic
Publications
On the expressive power of CNF formulas of bounded tree- and clique-width

On the expressive power of CNF formulas of bounded tree- and clique-width,10.1016/j.dam.2010.09.007,Discrete Applied Mathematics,Irénée Briquel,Pascal

On the expressive power of CNF formulas of bounded tree- and clique-width   (Citations: 2)
BibTex | RIS | RefWorks Download
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 particular 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 polynomial 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 arguments 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⊈FP/poly.
Journal: Discrete Applied Mathematics - DAM , vol. 159, no. 1, pp. 1-14, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: