Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème de comptage
Résumé
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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.