title: Sharp-P-complet
text: # Sharp-P-complet
  
  #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 et a été le premier étudié à la fin des années 70 par Leslie Valiant. 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
  
  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.
  
  