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èmes 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.

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''arbre de calcul avec le mot x en entrée. Dans l'exemple f(miaou) = 4.

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.

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 donné, un 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[3].

Plus précisément[4], pour un alphabet quelconque $\Sigma$ , une fonction $f:\Sigma ^{*}\rightarrow \mathbb {N}$ est dans #P, s'il existe un langage A dans la classe P, et un polynôme $p(n)$ tel que:

\forall x\in \Sigma ^{*},f(x)=Card(\{y\in \Sigma ^{p(|x|)}|(x,y)\in A\})

Problèmes complets

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, 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. 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, 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 P^#P inclus dans PH). 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

Sharp-P a été définie par Leslie Valiant en 1979[5].

Notes et références

Ou encore pound P ou number P, voir Johnson 1992 p. 107.
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.
Lane A. Hemaspaandra et Mitsunori Ogihara, « Annexe A10 : #P: Counting functions », dans The complexity theory companion, Springer, 2002, p. 286-287
Cette formulation est issue de : Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 9 (« Comptage »)
D'après (Hemaspaandra et Ogihara 2002). Article original : Valiant 1979.

Bibliographie

Lane A. Hemaspaandra et Mitsunori Ogihara, « Annexe A10 : #P: Counting functions », dans The complexity theory companion, Springer, 2002, p. 286-287

Leslie G. Valiant, « The Complexity of Computing the Permanent », Theor. Comput. Sci., vol. 8,‎ 1979, p. 189-201

David S. Johnson, « A catalog of complexity classes », dans Algorithms and complexity, Elsivier, 1992, 2^e éd. (1^re éd. 1990) (ISBN 0444880712)

Liens externes

(en) La classe #P sur le Complexity Zoo

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Ou encore pound P ou number P, voir Johnson 1992 p. 107.

[2] 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.

[tctc-3] Lane A. Hemaspaandra et Mitsunori Ogihara, « Annexe A10 : #P: Counting functions », dans The complexity theory companion, Springer, 2002, p. 286-287

[4] Cette formulation est issue de : Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 9 (« Comptage »)

[5] D'après (Hemaspaandra et Ogihara 2002). Article original : Valiant 1979.