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 (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 ?

#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

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

Calcul du permanent

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

${\displaystyle \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 ${\displaystyle \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

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

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

• Portail de l'informatique théorique