On the expressive power of planar perfect matching and permanents of bounded treewidth matrices

Abstract : 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. They are defined using non-uniform sequences of arithmetic circuits and provides a framework to study the complexity for sequences of polynomials. Prominent examples of difficult (that is, VNP-complete) problems in this model includes the permanent and hamiltonian polynomials. While the permanent and hamiltonian polynomials in general are difficult to evaluate, there have been research on which special cases of these polynomials admits efficient evaluation. For instance, Barvinok has shown that if the underlying matrix has bounded rank, both the permanent and the hamiltonian polynomials can be evaluated in polynomial time, and thus are in VP. Courcelle, Makowsky and Rotics have shown that for matrices of bounded treewidth several difficult problems (including evaluating the permanent and hamiltonian polynomials) can be solved efficiently. An earlier result of this flavour is Kasteleyn's theorem which states that the sum of weights of perfect matchings of a planar graph can be computed in polynomial time, and thus is in VP also. For general graphs this problem is VNP-complete. In this paper we investigate the expressive power of the above results. 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.
Type de document :
Pré-publication, Document de travail
14 pages. 2007
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00149062
Contributeur : Laurent Lyaudet <>
Soumis le : vendredi 25 mai 2007 - 12:28:12
Dernière modification le : mardi 24 avril 2018 - 13:52:24
Document(s) archivé(s) le : jeudi 8 avril 2010 - 17:43:10

Fichiers

formulas.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00149062, version 1
  • ARXIV : 0705.3751

Collections

Citation

Uffe Flarup, Pascal Koiran, Laurent Lyaudet. On the expressive power of planar perfect matching and permanents of bounded treewidth matrices. 14 pages. 2007. 〈ensl-00149062〉

Partager

Métriques

Consultations de la notice

146

Téléchargements de fichiers

83