Voir la source de Sharp-P

{{Titre incorrect|#P}}
[[Fichier:SharpP executions.png|vignette|Considérons une machine de Turing non-déterministe en temps polynomial pour le problème dans NP correspondant un problème 'calculer f(x)' dans #P. f(x) est le nombre d'exécutions acceptantes dans l<nowiki>''</nowiki>arbre de calcul avec le mot x en entrée. Dans l'exemple f(miaou) = 4.]]
'''#P''', prononcé ''sharp P'' (ou ''dièse-P''<ref>Ou encore ''{{langue|en|pound P}}'' ou ''{{langue|en|number P}}'', voir {{harvsp|Johnson|1992}} p. 107.</ref>) est la classe des fonctions qui comptent le nombre de [[Certificat (complexité)|certificats]] d'un [[problème de décision]] qui est dans la classe '''NP'''. La classe '''#P''' tient une place à part dans la théorie de la complexité, car ce n'est pas une classe de [[problème de décision|problèmes de décision]] mais une classe de fonctions de comptage de solutions<ref>Une ''fonction de comptage'' est une fonction ''f: Σ* → ℕ'', un mot ''x ∈  Σ*'' correspond à une question et ''f(x)'' correspond aux nombres de réponses positives à cette question, autrement dit ''f(x)'' compte les solutions au problème posé par ''x''.</ref>. Une fonction ''f'' est dans '''#P''' s'il existe une [[machine de Turing non-déterministe]] M fonctionnant en temps polynomial telle que pour toute instance ''x'', ''f(x)'' soit le nombre d'exécutions de M acceptant ''x'' comme mot d'entrée.

== Exemples de problèmes ==

Un problème de décision de la classe '''NP''' est souvent de la forme "Y a-t-il des instances qui satisfont certaines contraintes ?". A contrario, les problèmes de la classe '''#P''' correspondants posent la question "Combien y a-t-il d'instances qui satisfont certaines contraintes ?". Le tableau suivant met en correspondance des exemples de problèmes de décision de la classe '''NP''' avec leurs problèmes de comptage correspondants dans la classe '''#P'''.
{| class="wikitable"
!Problème de décision dans NP
!Problème de comptage dans #P
|-
|Y a-t-il un sous-ensemble d'une liste d'entiers dont la somme est égale à zéro ? (Problème de la somme d'un sous-ensemble)
|Combien y a-t-il de sous-ensembles d'une liste d'entiers dont la somme est égale à zéro ?
|-
|Y a-t-il, dans un [[graphe (théorie des graphes)|graphe]] donné, un [[graphe hamiltonien|cycle hamiltonien]] avec un coût inférieur à k ? (variante du [[problème du voyageur de commerce]])
|Combien de cycles hamiltoniens d'un graphe donné ont un coût inférieur à k ?
|-
|Y a-t-il une assignation de variables qui rend vraie une formule de la logique propositionnelle donnée (exprimée en général sous [[forme normale conjonctive]]) ? ([[Problème SAT]])
|Combien d'assignations de variables rendent vraie une formule de la logique propositionnelle donnée ?
|}

== Définition formelle ==

La classe #P peut être définie comme l'ensemble des fonctions ''f'' telles qu'il existe une machine de Turing M non déterministe en temps polynomial, telle que pour tout ''x'', ''f(x)'' est égale au nombre de chemins acceptants pour M sur l'entrée ''x''<ref name = tctc>
{{chapitre
 | titre chapitre = Annexe A10 : #P: Counting functions
 | titre ouvrage = The complexity theory companion
 | nom1 = Hemaspaandra | prénom1 = Lane A.
 | nom2 = Ogihara | prénom2 =  Mitsunori
 | année = 2002
 | éditeur = Springer
 | passage = 286-287}} </ref>.

Plus précisément<ref>Cette formulation est issue de : {{Complexité algorithmique (Perifel)|numéro chapitre=9|titre chapitre=Comptage}}</ref>, pour  un alphabet quelconque <math>\Sigma</math>, une fonction <math>f: \Sigma^* \rightarrow \mathbb{N}</math> est dans #P, s'il existe un langage A dans la classe [[P (complexité)|P]], et un polynôme <math>p(n)</math> tel que:
:<math>\forall x \in \Sigma^*, f(x)=Card(\{y\in \Sigma^{p(|x|)}|(x,y)\in A \})</math>

== Problèmes complets ==
{{article détaillé|Sharp-P-complet}}

Les problèmes #P-complets sont considérés comme les problèmes de comptage les plus difficiles de la classe #P. Par exemple, le problème du calcul du [[permanent (mathématiques)|permanent]], qui peut-être vu comme un problème de comptage, est un problème #P-complet.

== Relations avec les autres classes ==
=== Liens avec P et NP ===
Clairement, un problème '''#P''' doit être au moins aussi dur que le problème qui lui correspond dans '''NP''', puisque savoir combien il y a de solutions nous dit, en particulier, s'il y a au moins une solution. Ainsi, le problème de la classe '''#P''' correspondant à un problème [[NP-complet]] doit être [[NP-difficile]].

Curieusement, certains problèmes de '''#P''' qui sont considérés comme difficiles correspondent à des problèmes faciles, de la classe '''[[P (complexité)|P]]'''. Par exemple le problème du calcul du permanent est #P-complet alors que le problème d'existence associé est dans P.

=== Autres classes ===
Une classe de problèmes de décision proche de '''#P''' est '''[[PP (complexité)|PP]]''', qui est la classe des problèmes décidés par une machine de Turing non-déterministe en temps polynomial, où si x est une instance positive alors la majorité (plus de la moitié) des exécutions depuis x sont acceptantes. Ceci répond à la partie la plus significative du problème de '''#P''' correspondant. La classe des problèmes de décision {{lien|trad=Parity P|fr=Parity P|texte=⊕P}} concerne, au contraire, la partie la moins significative du problème '''#P''' correspondant.

Une conséquence du [[théorème de Toda]] est qu'une machine en temps polynomial disposant d'un oracle de la classe '''#P''' peut résoudre n'importe quel problème de la [[hiérarchie polynomiale]] '''PH''' (c'est-à-dire que '''PH''' est inclus dans '''P'''<sup>'''#P'''</sup>). En fait, la machine à temps polynomial n'a besoin que d'une requête à l'oracle '''#P''' pour résoudre n'importe quel problème de  '''PH'''. C'est une indication de la difficulté à résoudre en pratique des problèmes '''#P'''-complets.

== Historique ==
'''#P''' a été définie par [[Leslie Valiant]] en 1979<ref>D'après {{harv|Hemaspaandra|Ogihara|2002}}. Article original : {{harvsp|Valiant|1979}}.</ref>.

== Notes et références ==
<references />

== Bibliographie ==
* {{chapitre
 | titre chapitre = Annexe A10 : #P: Counting functions
 | titre ouvrage = The complexity theory companion
 | nom1 = Hemaspaandra | prénom1 = Lane A.
 | nom2 = Ogihara | prénom2 = Mitsunori
 | année = 2002
 | éditeur = Springer
 | passage = 286-287}}

* {{article 
 | prénom1 = Leslie G. | nom1 = Valiant
 | titre     = The Complexity of Computing the Permanent
 | périodique   = Theor. Comput. Sci.
 | volume    = 8
 | année      = 1979
 | passage     = 189-201}}

* {{chapitre
 | titre chapitre = A catalog of complexity classes
 | titre ouvrage = Algorithms and complexity
 | nom = Johnson | prénom = David S. | lien auteur = David S. Johnson
 | année = 1992
 | numéro d'édition = 2
 | éditeur = Elsivier
 | année première édition = 1990
 | isbn = 0444880712}}

== Liens externes ==
* {{Complexity Zoo|fin=Symbols#sharpp|nom=#P}}

{{Palette|Théorie de la complexité}}
{{Portail|informatique théorique}}

[[Catégorie:Classe de complexité]]