Sharp-P-complet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Titre correct : « #P-complet »

En raison de limitations techniques, la typographie souhaitable du titre n’a pu être restituée correctement.

Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ne cite pas suffisamment ses sources (décembre 2012).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » (modifier l'article, comment ajouter mes sources ?).

#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éfini 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 s'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, Elsevier,‎ , 2e éd. (1re éd. 1990) (ISBN 0444880712)
  2. Leslie G. Valiant, « The Complexity of Computing the Permanent », Theor. Comput. Sci., vol. 8,‎ , p. 189-201