Sharp-P-complet
Titre correct : « #P-complet ».
En raison de limitations techniques, la typographie souhaitable du titre n’a pu être restituée correctement.
Cet article est une ébauche concernant l’informatique théorique et les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Cet article ne cite pas suffisamment ses sources ().
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 ».
En pratique : Quelles sources sont attendues ? 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
- .
Ce problème est en fait un problème de comptage, puisque le permanent est égal au nombre de permutations tel que . 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 :
- Combien une formule FND donnée admet-elle d'assignements valides ?
- Combien une formule 2-SAT donnée admet-elle d'assignements valides ?
- Combien de couplages parfaits admet un graphe biparti donné ?
- Combien de k-coloriages admet un graphe donné ?
Question ouverte
[modifier | modifier le code]S'il existe un algorithme polynomial pour un problème #P-complet, alors P=PH, et donc P=NP. À ce jour (2022), aucun tel algorithme n'est connu.
Notes et références
[modifier | modifier le code]- 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)
- Leslie G. Valiant, « The Complexity of Computing the Permanent », Theor. Comput. Sci., vol. 8, , p. 189-201
