Sharp-P-complet

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

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

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.

• Portail de l'informatique théorique