Computational Complexity - Research Seminar
Laurent Lyaudet (Université d'Orléans): Graph Covers and Algebraic Complexity
July 15, 2008, 10:15 a.m.
E 1 3, Room 415
Some 25 years ago Valiant introduced an algebraic model of computation in order to study the complexity of evaluating families of polynomials. The theory was introduced along with the complexity classes VP and VNP which are 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 work we investigate the expressive power of easy special cases of these polynomials. We take a graph theoretic approach to deal with permanent and hamiltonian polynomials using their combinatorial characterizations with directed cycle covers, hamiltonian circuits or perfect matchings. We show that the permanent and hamiltonian polynomials for matrices of bounded treewidth (pathwidth) 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 (bipartite) planar graphs. Last, for matrices of bounded weighted cliquewidth we show membership in VP for these polynomials.