En théorie de la complexité et en théorie de la calculabilité, un problème de comptage est un type particulier de problème algorithmique. Étant donné un problème algorithmique consistant à trouver une solution, on peut définir le problème de comptage associé, qui consiste à calculer le nombre de solutions. Des classes de complexité spécifiques existent pour les problèmes de comptage, dont la plus connue #P qui est l'analogue de la classe NP pour les problèmes de décision.
Exemple introductif
Un exemple classique de problème de décision est le problème 3-SAT qui consiste à décider si une formule en forme normale conjonctive où les clauses ont au plus 3 littéraux est satisfiable ou non. Le problème de recherche associé consiste à trouver une solution si elle existe. Le problème de comptage, appelé #3SAT, consiste à calculer le nombre de solutions.
Définition formelle Si R est un problème de recherche, alors
est la fonction de comptage correspondante ; elle compte le nombre de solutions en y du problème pour une valeur de x donnée.
désigne le problème de décision correspondant.
On distingue comme d'usage c R qui est un problème de recherche de #R qui est un problème de décision ; cependant c R peut être réduit au sens de Cook à # R (pour une réduction C appropriée) en utilisant une recherche dichotomique. C'est la définition de # R donnée ci-dessus, plutôt que comme graphe de c R, qui rend possible la recherche binaire.
Réductions
Les réductions utilisées pour les problèmes de décision ne peuvent pas être directement utilisées pour les problèmes de comptage. À la place on introduit la notion de réduction parcimonieuse et la notion plus générale de réduction de comptage..
Soient deux fonctions. On dit que se réduit à par une réduction parcimonieuse s’il existe une fonction calculable en temps polynomial telle que, pour tout , on ait .
Une définition plus générale est : Soient deux fonctions. On dit que se réduit à par une réduction de comptage s’il existe deux fonctions calculables en temps polynomial telle que, pour tout , on ait .
La fonction de sortie s fait de cette réduction de comptage l’analogue d’une réduction de Turing.
Classe de complexité de comptage Si NX est une classe de complexité associée à des machines non déterministes, alors #X = { #R | R ∈ NX } est l'ensemble des problèmes de comptage associés à chaque problème de recherche dans NX . En particulier, #P est la classe des problèmes de comptage associés aux problèmes de recherche NP. Tout comme la classe NP a des problèmes NP-complets via des réductions many-one appropriées, la classe #P a des problèmes complets via des réductions parcimonieuses, qui sont des transformations de problèmes qui préservent le nombre de solutions. Par exemple le problème #3SAT cité plus haut est #P-complet. Un autre exemple est #CLIQUE, qui consiste étant donné un graphe G, et un entier k, à calculer le nombre de cliques de taille k dans le graphe G.
Le problème #P-complet le plus connu est le calcul du permanent..
Théorème de Toda
Un théorème remarquable à propos des problèmes de comptage est le théorème de Toda. Intuitivement, ce théorème dit que la classe #P est aussi puissante que toute la hiérarchie polynomiale. Plus formellement, la hiérarchie polynomiale PH, est incluse dans la classe P muni d'un oracle #P: PH ⊆ P#P.
Notes et références
Voir aussi
GapP
Liens externes
« counting problem » sur Planetmath « counting complexity class » sur Planetmath
Catégorie:Problème algorithmique