♯P-complet - ♯P-complete

Les problèmes #P-complets (prononcés "sharp P complete" ou "number P complete") forment une classe de complexité en théorie de la complexité computationnelle . Les problèmes de cette classe de complexité sont définis par les deux propriétés suivantes :

• Le problème est dans #P , la classe de problèmes qui peut être définie comme le comptage du nombre de chemins acceptants d'une machine de Turing non déterministe en temps polynomial .
• Le problème est #P -difficile, ce qui signifie que tous les autres problèmes de #P ont une réduction de Turing ou une réduction de comptage en temps polynomial . Une réduction de comptage est une paire de transformations en temps polynomial des entrées de l'autre problème aux entrées du problème donné et des sorties du problème donné aux sorties de l'autre problème, permettant à l'autre problème d'être résolu en utilisant n'importe quel sous-programme pour le problème donné. problème. Une réduction de Turing est un algorithme pour l'autre problème qui effectue un nombre polynomial d'appels à un sous-programme pour le problème donné et, en dehors de ces appels, utilise le temps polynomial. Dans certains cas , des réductions parcimonieuses , un type de réduction plus spécifique qui préserve le nombre exact de solutions, sont utilisées.

Un algorithme en temps polynomial pour résoudre un problème #P-complet, s'il existait, résoudrait le problème P contre NP en impliquant que P et NP sont égaux. Aucun algorithme de ce type n'est connu, et aucune preuve n'est connue qu'un tel algorithme n'existe pas.

Exemples

Exemples de problèmes #P-complets :

• Combien d'affectations de variables différentes satisferont une formule booléenne générale donnée ? ( #SAT )
• Combien d'affectations de variables différentes satisferont une formule DNF donnée ?
• Combien d'affectations de variables différentes satisferont un problème de 2-satisfiabilité donné ?
• Combien y a-t-il de correspondances parfaites pour un graphe bipartite donné ?
• Quelle est la valeur de la permanente d'une matrice donnée dont les entrées sont 0 ou 1 ? (Voir #P-complétude de 01-permanent .)
• Combien y a-t-il de colorations de graphes utilisant k couleurs pour un graphe particulier G ?
• Combien y a-t-il d' extensions linéaires différentes pour un ensemble partiellement ordonné donné , ou, de manière équivalente, combien d' ordres topologiques différents y a-t-il pour un graphe acyclique orienté donné ?

Ce sont tous nécessairement des membres de la classe #P également. À titre de non-exemple, considérons le cas des solutions de comptage d'un problème de 1-satisfiabilité : une série de variables qui sont chacune individuellement contraintes, mais n'ont aucune relation les unes avec les autres. Les solutions peuvent être comptées efficacement, en multipliant le nombre d'options pour chaque variable isolément. Ainsi, ce problème est dans #P , mais ne peut pas être #P-complet à moins que #P = FP . Ce serait surprenant, car cela impliquerait que P = NP = PH .

Problèmes faciles avec les versions de comptage difficiles

Certains problèmes #P-complets correspondent à des problèmes faciles (en temps polynomial ). Déterminer la satisfiabilité d'une formule booléenne dans DNF est facile : une telle formule est satisfiable si et seulement si elle contient une conjonction satisfiable (celle qui ne contient pas de variable et sa négation), alors que compter le nombre d'affectations satisfaisantes est #P- Achevée. De plus, décider de la 2-satisfiabilité est plus facile que de compter le nombre d'affectations satisfaisantes. Le tri topologique est facile contrairement au comptage du nombre de tris topologiques. Une seule correspondance parfaite peut être trouvée en temps polynomial, mais compter toutes les correspondances parfaites est #P-complet. Le problème de comptage d'appariement parfait était le premier problème de comptage correspondant à un problème P facile montré comme #P-complet, dans un article de 1979 de Leslie Valiant qui définissait également la classe #P et les problèmes #P-complet pour la première fois.

Approximation

Il existe des algorithmes probabilistes qui renvoient de bonnes approximations à certains problèmes #P-complets avec une probabilité élevée. C'est une des démonstrations de la puissance des algorithmes probabilistes.

De nombreux problèmes #P-complets ont un schéma d'approximation aléatoire entièrement polynomial , ou "FPRAS", qui, de manière informelle, produira avec une probabilité élevée une approximation à un degré arbitraire de précision, en temps polynomial par rapport à la taille du problème et du degré de précision requis. Jerrum , Valiant et Vazirani ont montré que chaque problème #P-complet a soit un FPRAS, soit est essentiellement impossible à approximer ; s'il existe un algorithme en temps polynomial qui produit systématiquement une approximation d'un problème #P-complet qui se situe dans un rapport polynomial de la taille de l'entrée de la réponse exacte, alors cet algorithme peut être utilisé pour construire un FPRAS.

Les références

Lectures complémentaires

• Vazirani, Vijay V. (2003). Algorithmes d'approximation . Berlin : Springer. ISBN 3-540-65367-8.