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.

#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.

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

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 ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Définition modifier

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

Calcul du permanent modifier

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

\mathrm {perm} (A)=\sum _{\sigma }\Pi _{i=1}^{n}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}^{n}A_{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

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

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

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

Portail de l'informatique théorique

[1] Cette partie est inspiré de : David S. Johnson, « A catalog of complexity classes », dans Algorithms and complexity, Elsevier, 1992, 2^e éd. (1^re éd. 1990) (ISBN 0444880712)

[2] Leslie G. Valiant, « The Complexity of Computing the Permanent », Theor. Comput. Sci., vol. 8,‎ 1979, p. 189-201

[1]

[2]