Sharp-P

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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èmes de décision qui est dans la classe NP. #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[modifier | modifier le code]

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

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

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

Autres classes[modifier | modifier le code]

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

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

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

  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, , p. 286-287
  4. Cette formulation est issue de : Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 9 (« Comptage »)
  5. 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, , p. 286-287
  • Leslie G. Valiant, « The Complexity of Computing the Permanent », Theor. Comput. Sci., vol. 8,‎ , p. 189-201
  • David S. Johnson, « A catalog of complexity classes », dans Algorithms and complexity, Elsivier, , 2e éd. (1re éd. 1990) (ISBN 0444880712)

Liens externes[modifier | modifier le code]