Sharp-P

Un article de Wikipédia, l'encyclopédie libre.

Titre correct : « #P »

En raison de limitations techniques, la typographie souhaitable du titre n’a pu être restituée correctement.

#P, prononcé "sharp P", est une classe de complexité dans la théorie de la complexité. C'est l'ensemble des problèmes associés aux problèmes de décision de la classe NP. Contrairement à la plupart des classes de complexité les plus connues, ce n'est pas une classe de problèmes de décision mais une classe de problèmes de fonction.

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 ?

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.

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 sharp-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 polynômial, 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 polynômial 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 toute entière. En fait, la machine à temps polynômial 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.