Au-dessus de #P et comptage des problèmes de recherche

Je lisais l'article de wikipedia sur le problème des huit reines. Il est indiqué qu'il n'existe pas de formule connue pour le nombre exact de solutions. Après quelques recherches, j'ai trouvé un article intitulé "Sur la dureté des problèmes de comptage des mappings complets". Dans cet article, il y a un problème, qui s'avère au plus aussi dur que #queens, qui est au-delà de #P. Pour avoir un aperçu du nombre de #queens comptés de manière exhaustive dans l'article de wikipedia, ils semblent à peu près super exponentiels.

Je veux demander s'il y a un nom pour cette classe ou s'il y a en général des problèmes de comptage appartenant aux classes au dessus de #P (avec une décision pas dans PSPACE bien sûr car ce serait évident).

Enfin, je veux demander s'il y a d'autres résultats connus pour d'autres problèmes de recherche, comme trouver un point tricolore dans le Lemme de Sperner par exemple (PPAD complet).

Si la fonction f est dans #P, alors étant donné une chaîne d'entrée x d'une certaine longueur N, la valeur f (x) est un nombre non négatif limité par . (Cela découle de la définition, en termes de nombre de chemins d'acceptation d'un vérificateur NP.)$2^{poly(N)}$

Cela signifie que de nombreuses fonctions f se trouvent en dehors de #P pour des raisons sans intérêt --- soit parce que f est négatif, soit, dans le cas que vous mentionnez, parce que la fonction croît plus vite que . Mais pour le problème des n -queens tel que modélisé dans l'article, ce n'est qu'un artefact de la décision des auteurs de laisser la valeur d'entrée n être codée en binaire. Si l'entrée attendue était la chaîne unaire 1 n , alors f ( 1 n ) : = (nombre de n valides$2^{poly(N)}$$n$$n$$1^n$$f(1^n) :=$$n$-queen configurations) serait certainement en #P, par un simple vérificateur NP qui vérifie la validité d'une configuration donnée.

Si vous voulez explorer certaines fonctions qui (conjecturellement) se trouvent en dehors de #P pour des raisons plus intéressantes, considérez par exemple celles-ci:

• UNSAT: si ψ est une formule booléenne insatisfaisante, sinon f ( ψ ) : = $f(\psi) := 1$$\psi$$f(\psi) := 0$ . Cette fonction n'est pas dans #P, sauf si NP = coNP. Ce n'est probablement pas non plus dans la classe de comptage plus générale GapP; c'est-à-dire que UNSAT n'est probablement pas la différence f - g de deux fonctions #P. Cependant, il se trouve dans la classe de complexité de comptage plus générale , qui contient en fait la hiérarchie polynomiale entière par le théorème de Toda.$P^{\# P}$

Vous pourriez ne pas aimer cet exemple car ce n'est pas un "problème de comptage" naturel. Mais les deux prochains seront:

• le nombre d'affectations à x telles que la formule booléenne ψ ( x , $f(\psi(x, y)) :=$$x$$\psi(x, \cdot)$$y$

• $f(\psi(x, y)) :=$$x$$y$$\psi(x, y) = 1$

Les deux derniers problèmes ne sont pas connus pour être calculés efficacement même avec un accès Oracle à #P. Cependant, ils sont calculables dans la soi-disant "hiérarchie de comptage". Pour certains problèmes plus naturels classés dans cette classe, voir par exemple ce document récent.

Compter les équilibres de Nash est apparemment # P-difficile, voir ici . De plus, même les problèmes où le problème de recherche est facile peuvent être difficiles à compter #P, par exemple, compter les correspondances parfaites.

$\#PSPACE$$\#EXPTIME$

La complexité des modèles de comptage de la logique temporelle en temps linéaire par Hazem Torfah, Martin Zimmermann