Sharp-P#P, prononcé sharp P (ou dièse-P[1]) est la classe des fonctions qui comptent le nombre de 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èmes de décision mais une classe de fonctions de comptage de solutions[2]. 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èmesUn 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.
Définition formelleLa 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[3]. Plus précisément[4], pour un alphabet quelconque , une fonction est dans #P, s'il existe un langage A dans la classe P, et un polynôme tel que: Problèmes completsLes 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, qui peut-être vu comme un problème de comptage, est un problème #P-complet. Relations avec les autres classesLiens avec P et NPClairement, 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. Par exemple le problème du calcul du permanent est #P-complet alors que le problème d'existence associé est dans P. Autres classesUne classe de problèmes de décision proche de #P est 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 ⊕P (en) 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#P). 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[5]. Notes et références
Bibliographie
Liens externes |