Sharp-P

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

Vous avez de nouveaux messages (diff^?).

En raison de limitations techniques, la typographie souhaitable du titre, « #P », n'a pu être restituée correctement ci-dessus.

#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. S'il est facile de compter les réponses, alors il doit être facil de déterminer s'il y a des réponses. Il suffit pour cela de les compter de voir sir le compte est supérieur à zéro. En conséquence, 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 soluble 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 de problèmes de décision ⊕P pose au contraire la question concernant 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 toute 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.