zbMATH — the first resource for mathematics

On the expressive power of planar perfect matching and permanents of bounded treewidth matrices. (English) Zbl 1141.68418
Tokuyama, Takeshi (ed.), Algorithms and computation. 18th international symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-77118-0/pbk). Lecture Notes in Computer Science 4835, 124-136 (2007).
Summary: Valiant introduced some 25 years ago an algebraic model of computation along with the complexity classes VP and VNP, which can be viewed as analogues of the classical classes P and NP. Prominent examples of difficult (that is, VNP-complete) problems in this model includes the permanent and hamiltonian polynomials. In this paper we investigate the expressive power of easy special cases of these polynomials. We show that the permanent and hamiltonian polynomials for matrices of bounded treewidth both are equivalent to arithmetic formulas. Also, arithmetic weakly skew circuits are shown to be equivalent to the sum of weights of perfect matchings of planar graphs.
For the entire collection see [Zbl 1136.68011].

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI