Qual é a complexidade de contar o número de soluções de um problema do P-Space Complete? E quanto às classes de maior complexidade?

Você está perguntando muito em uma pergunta!

#PSPACE é igual à classe de funções que pode ser calculada no espaço polinomial (FPSPACE).

@Tsuyoshi Isso é verdade. No entanto, a maioria das perguntas feitas, se não todas, pode ser reformulada como uma única pergunta geral: existem classes de contagem para classes superiores a $NP$ (como se pode observar na definição de # $P$ ) e os resultados conhecidos se aplicam?

@ Tayfun Pay: Não sei bem o que você quer dizer com classes determinísticas como PSPACE, EXP, EXPSPACE. A noção de "número de soluções" geralmente está intimamente ligada ao não-determinismo - desde então, você pode perguntar sobre o número de caminhos aceitantes - ou quantificadores / projeções existenciais. No caso do PSPACE, é claro, você pode usar a definição de quantificadores alternados - mas é necessário especificar quais quantificadores você deseja contar - ou o fato de que NPSPACE = PSPACE.

Como vários comentários mencionados, não está totalmente claro o que você quer dizer com #PSPACE. A melhor aposta seria usar o analógico acolchoado de #L, que é bem estudado. Como #L está contido no DSPACE (log ^ 2 n), isso implicaria que # PSPACE = PSPACE, como @TsuyoshiIto mencionado acima. (Estou ignorando aqui a distinção formal entre imaterial problemas de decisão e funções.)

Isso não está coberto pelos comentários de Tsuyoshi e Noam acima?

É isso que você realmente quer dizer? Se #P = #PSPACE, isso não implica que PSPACE P ? Eu não acredito que isso seja conhecido. # $\subseteq$$^{\#\mathrm{P}}$

@ PeterShor Estou bastante certo de que Daniel significa isso mathoverflow.net/a/12608/35733 . Mas meu palpite (não verificado) é que um problema # PSPACE-complete é contar o número de atribuições satisfatórias de um QBF fixo, não contar o número de quantificações satisfatórias de um determinado CNF.

Não, eu quis dizer que o número de quantificações válidas de um determinado cnf é igual ao número de atribuições satisfatórias do cnf, dada uma ordem fixa das variáveis. É muito interessante que mudar a ordem das variáveis ​​altere os qbfs válidos, mas não o número total de qbfs válidos.