- Sharp-P
-
#P, prononcé "sharp P" (ou "dièse-P"), est une classe de complexité. Contrairement à la plupart des autres classes de complexité, ce n'est pas une classe de problèmes de décision mais une classe de fonctions calculables. Il s'agit de compter le nombre de solutions du problème plutôt que le temps de calcul de la solution. Plus formellement, un problème est dans #P s'il existe une machine de Turing non-déterministe en temps polynomial qui, pour chaque instance I du problème, a un nombre d'états finaux acceptables exactement égal au nombre de solutions distinctes à l'instance I.
Formulations
Un problème de la classe NP est souvent de la forme, "Y a-t-il des solutions qui satisfont à certaines contraintes ?" Par exemple :
- 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)
- Y a-t-il, dans un graphe donné, un cycle Hamiltonien avec un coût inférieur à 100 ? (Problème du voyageur de commerce)
- Y a-t-il un assignement de variables qui vérifie une formule donnée (exprimée en général sous forme normale conjonctive) ? (Problème SAT)
Les problèmes de la classe #P correspondants posent la question "Combien y a-t-il" plutôt que "Y a-t-il". Par exemple :
- Combien y a-t-il de sous-ensembles d'une liste d'entiers dont la somme est égale à zéro ?
- Combien de cycles Hamiltoniens d'un graphe donné ont un coût inférieur à 100 ?
- Combien d'assignements de variables satisfont à une formule donnée ?
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. Pour plus d'informations sur le sujet, voyez #P-complet.
La classe de problèmes de décision la plus proche de #P est PP, qui est la classe des problèmes solubles par une machine de Turing non-déterministe en temps polynomial, dont la majorité (plus de la moitié) des états finaux sont acceptables. Ceci répond à la partie la plus significative du problème de #P correspondant. La classe des problèmes de décision ⊕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, (P#P), peut résoudre n'importe quel problème de PH, c’est-à-dire de la hiérarchie polynomiale tout entière. 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 l'extrême difficulté qu'il y a à résoudre exactement des problèmes #P-complets.
Références
- Complexity Zoo: #P (en)
Wikimedia Foundation. 2010.
