Existe um oráculo

8

fundo

Sabemos que .P#PPSPACE

Além disso, sabemos pelo teorema de Toda que .PHP#P

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

Questão

Existe um oráculo tal que ?UMA(P#P)UMAPSPUMACEUMA

Michael Wehar
fonte
3
Eu acho que para a primeira parte, definir deve ser suficiente, certo? Não é verdade que PSPACE PSPACE = PSPACE ? UMA=PSPACEPSPACEPSPACE=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
5
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
1
@ MarkusBläser Acho que você deve postar isso como resposta.
Emil Jerabek

Respostas:

6

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

Existe um oráculo que separa de P S P A C E : Jacobo Toran, uma técnica combinatória para separar classes de complexidade de contagem, ICALP 1989. O melhor resultado para P P P que conheço é um resultado condicional de Heribert Vollmer: Relação polinomial tempo para profundidade constante. TCS, 207: 159-170, 1998.PPPSPACEPPP

Markus Bläser
fonte
Apenas para garantir que estamos na mesma página, é sabido que ? PPP=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? PPPP#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
2
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