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