Sharp-P

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

#P, prononcé sharp P (ou dièse-P[1]), est une classe de complexité. Contrairement à la plupart des autres classes de complexité, ce n'est pas une classe de problèmes de décision mais une classe de fonctions calculables. Il s'agit de compter le nombre de solutions du problème plutôt que le temps de calcul de la solution. 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.

Présentation[modifier | modifier le code]

Un problème de la classe NP est souvent de la forme, "Y a-t-il des solutions qui satisfont à certaines contraintes ?" Par exemple :

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'assignations de variables satisfont à une formule donnée ?

Définition formelle[modifier | modifier le code]

La classe #P peut être définie comme l'ensemble des fonctions f telles qu'il existe une machine de Turing non déterministe en temps polynomial N, telle que pour tout x, f(x) est égale au nombre de chemins acceptant pour N sur l'entrée x[2].

Plus précisément[3], 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[modifier | modifier le code]

Article détaillé : Sharp-P-complet.

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[modifier | modifier le code]

Liens avec P et NP[modifier | modifier le code]

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 dans #P alors que le problème d'existence associé est dans P.

Autres classes[modifier | modifier le code]

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 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 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 (en) 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 tout 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.

Historique[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

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

Bibliographie[modifier | modifier le code]

  • 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, 2e éd. (1re éd. 1990) (ISBN 0444880712)

Liens externes[modifier | modifier le code]