Existe um oráculo

fundo

Sabemos que . $P^{\#P} \subseteq PSPACE$

Além disso, sabemos pelo teorema de Toda que . $PH \subseteq P^{\#P}$

Para mais informações sobre , consulte aqui: https://en.wikipedia.org/wiki/Sharp-P $\#P$

Questão

Existe um oráculo tal que ? $A$ $(P^{\#P})^{A} \neq PSPACE^{A}$

cc.complexity-theory complexity-classes oracles relativization pspace Michael Wehar
fonte

Eu acho que para a primeira parte, definir

deve ser suficiente, certo? Não é verdade que

A = PSPACE

$A=\textrm{PSPACE}$

{PSPACE}^{PSPACE} = PSPACE

$\textrm{PSPACE}^{\textrm{PSPACE}} = \textrm{PSPACE}$

Michael Lampis

@ MichaelLampis Sim, se você contar o espaço na fita de consulta, isso soa certo para mim! :)

Michael Wehar

Ótimo, muito obrigado por apontar isso! Modifiquei a pergunta, removendo a parte mais fácil de encontrar um oráculo onde eles são iguais. :)

Michael Wehar

Existe um oráculo que separa o PP do PSPACE: Jacobo Toran, Uma técnica combinatória para separar classes de complexidade de contagem, ICALP 1989. O melhor resultado para P ^ PP que eu sei é um resultado condicional de Heribert Vollmer: relacionando o tempo polinomial à profundidade constante. TCS, 207: 159-170, 1998.

Markus Bläser

@ MarkusBläser Acho que você deve postar isso como resposta.

Emil Jerabek

Respostas:

A pedido popular, aqui está o meu comentário como resposta:

Existe um oráculo que separa de : Jacobo Toran, uma técnica combinatória para separar classes de complexidade de contagem, ICALP 1989. O melhor resultado para que conheço é um resultado condicional de Heribert Vollmer: Relação polinomial tempo para profundidade constante. TCS, 207: 159-170, 1998. $\mathrm{PP}$ $\mathrm{PSPACE}$ $\mathrm{P}^\mathrm{PP}$

Markus Bläser
fonte

Apenas para garantir que estamos na mesma página, é sabido que

P^{P P} = P^{# P}

$P^{PP} = P^{\#P}$

Michael Wehar

Parece simples que

, mas a outra direção parece um pouco complicada. Você faz algum tipo de pesquisa binária para calcular o número de soluções para um verificador?

P^{P P} \subseteq P^{# P}

$P^{PP} \subseteq P^{\#P}$

Michael Wehar

Sim, o zoológico de complexidade diz que eles são iguais. Além disso, acho que me lembro de provar isso em um curso de teoria da complexidade há alguns anos como um exercício. :)

Michael Wehar

O zoológico de complexidade também diz que minha pergunta principal é um problema em aberto. Desculpe, eu não percebi isso. Eu pensei que talvez alguém lá fora tivesse resolvido isso.

Michael Wehar