Sharp-P

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.

#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è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 ${\displaystyle \Sigma }$, une fonction ${\displaystyle f:\Sigma ^{*}\rightarrow \mathbb {N} }$ est dans #P, s'il existe un langage A dans la classe P, et un polynôme ${\displaystyle p(n)}$ tel que:

${\displaystyle \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 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

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

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