Um problema que está no PSPACE, mas não se sabe que está no PH?

8

Como sabemos, o Graph Isomorphism está em NP, mas não é conhecido como NP-Complete ou P-Complete. Fiquei me perguntando se existem problemas conhecidos no PSPACE, mas que não são PSPACE-Complete e não estão no PH?

Tayfun Pay
fonte
4
Algum problema completo no PSPACE? Talvez você faça a pergunta errada.
5501
1
Você está perguntando se PH = PSPACE?
Mohammad Al-Turkistany
11
Se você pretendia solicitar um problema análogo ao GI, talvez esteja solicitando um problema que não esteja no PH e não esteja completo no PSPACE. Os problemas completos para qualquer classe que não seja conhecida como PH, mas contida no PSPACE, funcionarão como exemplo. Portanto, tome qualquer completa problema para BQP, QMA, PP, etc.
Robin Kothari
7
Além disso, a teoria existencial dos reais é conhecida no PSPACE, mas não no PH.
Peter Shor
4
@Robin, @ Pedro, ambos são respostas, não comenta :)
Suresh Venkat

Respostas:

23

A teoria existencial dos reais é conhecido por ser contido em PSPACE, mas não se sabe se ele está contido em PH. Portanto, adote a teoria existencial dos reais ou qualquer um dos muitos problemas equivalentes.

Peter Shor
fonte
O que você quer dizer com problema completo? A teoria existencial dos reais é um problema único, não uma classe.
Emil Jerabek
1
@Emil: corrigido agora. Existem problemas equivalentes suficientes que também considero uma classe de complexidade, mas sou minoria aqui.
Peter Shor
Entendo, isso faz sentido.
Emil Jerabek
19

Qualquer problema de PP concluído é trivial no PSPACE, mas é claro que não se sabe que ele esteja completo. Também não sabemos se o PP está ou não contido no PH, embora decorra do teorema de Toda que o PH esteja contido em P . Acredito que o mesmo se aplica aos problemas de #P -complete.PP

Dai Le
fonte
18

Copiando meu comentário:

Se você pretendia pedir um problema análogo ao GI, talvez esteja solicitando um problema que não esteja no PH e não esteja completo no PSPACE. Os problemas completos para qualquer classe que não seja conhecida como PH, mas contida no PSPACE, funcionarão como exemplo. Portanto, resolva qualquer problema para BQP, QMA, PP, etc.

Robin Kothari
fonte
1

Qualquer problema que seja MP-Complete, A classe de problemas de decisão de tal modo que, para alguma função #P f, a resposta na entrada x é 'yes' se e somente se o bit do meio de f (x) for 1. [Definição é de Zoológico de complexidade].
Foi demonstrado que PH ⊆ MP ⊆ PSPACE.

Tayfun Pay
fonte
1

O problema do ParitySat é verificar se um problema do SAT possui um número ímpar de atribuições satisfatórias. O PH é redutível ao ParitySAT através de reduções aleatórias pelo trabalho de Toda. Esse é um problema de decisão claramente estritamente entre PH e PSACE, a menos que o PH entre em colapso.

Bin Fu
fonte
Sim, existem dois corolários do teorema de Toda, que afirma que ParityP e PP estão em PH, a menos que o PH caia em um nível finito.
Tayfun Pay