Problème de comptage (complexité) - Counting problem (complexity)

Dans la théorie de la complexité computationnelle et la théorie de la calculabilité , un problème de comptage est un type de problème de calcul . Si R est un problème de recherche, alors

${\ displaystyle c_ {R} (x) = \ vert \ {y \ mid R (x, y) \} \ vert \,}$

est la fonction de comptage correspondante et

${\ displaystyle \ #R = \ {(x, y) \ mid y \ leq c_ {R} (x) \}}$

désigne le problème de décision correspondant.

Notez que c _R est un problème de recherche tandis que # R est un problème de décision, cependant c _R peut être C Cook-réduit à # R (pour C approprié ) en utilisant une recherche binaire (la raison # R est définie comme elle est, plutôt que d'être le graphe de c _R , c'est rendre cette recherche binaire possible).

Compter la classe de complexité

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 NP a des problèmes NP-complets via des réductions plusieurs-une , #P a des problèmes complets via des réductions parcimonieuses , des transformations de problèmes qui préservent le nombre de solutions.

Voir également

• GapP

Liens externes

• "problème de comptage" . PlanetMath .
• "compter la classe de complexité" . PlanetMath .