On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth

Autor: Uffe Flarup, Laurent Lyaudet
Přispěvatelé: Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Jazyk: angličtina
Rok vydání: 2008
Předmět:
FOS: Computer and information sciences
Perfect matchings
Discrete Mathematics (cs.DM)
Computation
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Pathwidth
0102 computer and information sciences
02 engineering and technology
Computer Science::Computational Complexity
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Theoretical Computer Science
Combinatorics
symbols.namesake
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
0202 electrical engineering
electronic engineering
information engineering
Complexity class
Permanent
ComputingMilieux_MISCELLANEOUS
Mathematics
Discrete mathematics
Formulas
16. Peace & justice
Skew circuits
Planar graph
Hamiltonian
Cliquewidth
Treewidth
Computational Theory and Mathematics
010201 computation theory & mathematics
Bounded function
Theory of computation
symbols
020201 artificial intelligence & image processing
Hamiltonian (quantum mechanics)
Valiant's model
Computer Science - Discrete Mathematics
Zdroj: Theory of Computing Systems
Theory of Computing Systems, Springer Verlag, 2010, 46 (4), pp.761-791. ⟨10.1007/s00224-009-9241-3⟩
Flarup, U & Lyaudet, L 2008, ' On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth ', Paper presented at International Computer Science Symposium in Russia, Moskva, Russian Federation, 07/06/2008-12/06/2008 .
ISSN: 1432-4350
1433-0490
DOI: 10.1007/s00224-009-9241-3⟩
Popis: 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. Families of polynomials that are difficult to evaluate (that is, VNP-complete) includes the permanent and hamiltonian polynomials. In a previous paper the authors together with P. Koiran studied the expressive power of permanent and hamiltonian polynomials of matrices of bounded treewidth, as well as the expressive power of perfect matchings of planar graphs. It was established that the permanent and hamiltonian polynomials of matrices of bounded treewidth are equivalent to arithmetic formulas. Also, the sum of weights of perfect matchings of planar graphs was shown to be equivalent to (weakly) skew circuits. In this paper we continue the research in the direction described above, and study the expressive power of permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth or bounded cliquewidth. In particular, we prove that permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth express exactly arithmetic formulas. This is an improvement of our previous result for matrices of bounded treewidth. Also, for matrices of bounded weighted cliquewidth we show membership in VP for these polynomials.
21 pages
Databáze: OpenAIRE
Externí odkaz: