Problème de comptage

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

$c_R(x)=|\{y\mid R(x,y)\}|$

est la fonction de comptage correspondante ; elle compte le nombre de solutions en y du problème pour une valeur de x donnée.

$\mathrm{\#}R=\{(x,y)\mid y\le c_R(x)\}$

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 $f,g:{\mathrm{\Sigma }}^{*}\to \mathbb{Z}$ deux fonctions. On dit que $f$ se réduit à $g$ par une réduction parcimonieuse s’il existe une fonction $e:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}$ calculable en temps polynomial telle que, pour tout $x\in {\mathrm{\Sigma }}^{*}$, on ait $f(x)=g(e(x))$.

Une définition plus générale est : Soient $f,g:{\mathrm{\Sigma }}^{*}\to \mathbb{Z}$ deux fonctions. On dit que $f$ se réduit à $g$ par une réduction de comptage s’il existe deux fonctions $e,s:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}$ calculables en temps polynomial telle que, pour tout $x\in {\mathrm{\Sigma }}^{*}$, on ait $f(x)=s(x,g(e(x)))$.

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.

Voir aussi

• GapP

Liens externes

• « counting problem » sur Planetmath
• « counting complexity class » sur Planetmath