Sharp-P-complet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

#P-complet, prononcée "sharp P complet" ou "dièse P complet", est une classe de complexité en théorie de la complexité, un domaine de l'informatique théorique. plus précisément c'est l'ensemble des problèmes complets de la classe #P.

Définition[modifier | modifier le code]

Un problème X est dit #P-complet si et seulement s'il appartient à la classe #P, et si on peut réduire tout problème de #P à X par une réduction de comptage fonctionnant en temps polynomial. De manière équivalente, un problème X est #P-complet si et seulement s'il appartient à #P et si pour toute machine de Turing non déterministe, le problème consistant à calculer son nombre de chemins acceptants peut être réduit à X.

Problèmes[modifier | modifier le code]

Calcul du permanent[modifier | modifier le code]

Le calcul du permanent est l'un des problèmes #P-complet les plus connus[1] et a été le premier étudié à la fin des années 70 par Leslie Valiant[2]. Il est définit de la manière suivante :

Entrée : une matrice à coefficient dans 0-1 (ie une matrice binaire)
Réponse : la valeur du permanent de la matrice, c'est-à-dire perm(A)=\sum_{\sigma} \Pi^n_{i=1} A_{i, \sigma(i)}.

Ce problème est en fait un problème de comptage, puisque le permanent est égal au nombre de permutations tel que \Pi_{i=1}^nA_{i,\sigma(i)}=1. Remarquons que le problème de décision qui consiste à savoir si il existe une permutation mettant le produit à 1, est lui un problème de P, puisqu'il revient à chercher l'existence d'un couplage parfait dans un graphe biparti.

Autres problèmes[modifier | modifier le code]

Les problèmes suivants sont des exemples de problèmes #P-complets :

Question ouverte[modifier | modifier le code]

L'existence d'un algorithme polynomial pour un problème #P-complet impliquerait P=PH, et donc P=NP. Actuellement, aucun algorithme de la sorte n'est connu.

Notes et références[modifier | modifier le code]

  1. Cette partie est inspiré de : David S. Johnson, « A catalog of complexity classes », dans Algorithms and complexity, Elsivier,‎ 1992, 2e éd. (1re éd. 1990) (ISBN 0444880712)
  2. Leslie G. Valiant, « The Complexity of Computing the Permanent », Theor. Comput. Sci., vol. 8,‎ 1979, p. 189-201