Acima de #P e contando problemas de pesquisa

Eu estava lendo o artigo da Wikipedia sobre o problema das oito rainhas. Afirma-se que, não existe uma fórmula conhecida para o número exato de soluções. Após algumas pesquisas, encontrei um artigo chamado "Sobre a dureza de contar problemas de mapeamentos completos". Neste artigo, há um problema, que se mostra no máximo tão difícil quanto #queens, que está além do #P. Vislumbrando o número de rainhas contadas exaustivamente no artigo da Wikipedia, elas parecem superexponenciais.

Quero perguntar se existe um nome para esta classe ou se, em geral, há problemas de contagem pertencentes a classes acima de #P (com decisão que não está no PSPACE, é claro, porque seria óbvio).

Finalmente, quero perguntar se existem outros resultados conhecidos para outros problemas de pesquisa, como encontrar um ponto colorido no lema de Sperner, por exemplo (PPAD completo).

Se a função f estiver em #P, dada uma sequência de entrada x com algum comprimento N, o valor f (x) é um número não negativo delimitado por . (Isso segue da definição, em termos de número de caminhos aceitos de um verificador NP.)$2^{poly(N)}$

Isto significa que muitas funções f fora mentira de #P para desinteressante razões --- quer porque f é negativa, ou, no caso de mencionar, porque a função cresce mais depressa do que . Mas, para o problema n- rainhas, conforme modelado no artigo, esse é apenas um artefato da decisão dos autores de permitir que o valor de entrada n seja codificado em binário. Se a entrada esperada for a sequência unária 1 n , então f ( 1 n ) : = (número de n válido$2^{poly(N)}$$n$$n$$1^n$$f(1^n) :=$$n$-queen configurações) certamente estariam em #P, por um simples verificador NP que verifica a validade de uma determinada configuração.

Se você deseja explorar algumas funções que (conjecturalmente) estão fora do #P por razões mais interessantes, considere, por exemplo:

• UNSAT: se ψ for uma fórmula booleana insatisfatória; caso contrário, f ( ψ ) : = 0 . Esta função não está em #P, a menos que NP = coNP. Provavelmente, também não está na classe GapP de contagem mais geral; isto é, UNSAT provavelmente não é a diferença f - g de duas funções #P. No entanto, está na classe de complexidade de contagem mais geral P # P , que de fato contém toda a Hierarquia Polinomial pelo teorema de Toda.$f(\psi) := 1$$\psi$$f(\psi) := 0$$P^{\# P}$

Você pode não gostar desse exemplo porque não é um "problema de contagem" natural. Mas os próximos dois serão:

• o número de atribuições para x de modo que a fórmula booleana ψ ( x , ⋅ ) seja satisfatória para algumas configurações em y .$f(\psi(x, y)) :=$$x$$\psi(x, \cdot)$$y$

• o número de x tal que, para pelo menos metade de todo y , ψ ( x , y ) = 1 .$f(\psi(x, y)) :=$$x$$y$$\psi(x, y) = 1$

Os dois últimos problemas não são conhecidos por serem eficientemente computáveis, mesmo com o acesso da Oracle ao #P. No entanto, eles são computáveis ​​dentro da chamada "hierarquia de contagem". Para alguns problemas mais naturais classificados nesta classe, consulte, por exemplo, este artigo recente.

Contar os equilíbrios de Nash é aparentemente difícil, veja aqui . Além disso, mesmo os problemas em que o problema de pesquisa é fácil podem ser #P difíceis de contar, por exemplo, contar combinações perfeitas.

$\#PSPACE$$\#EXPTIME$

A complexidade dos modelos de contagem da lógica temporal temporal em tempo linear de Hazem Torfah, Martin Zimmermann