É ?

Sabemos que o primeiro nível da hierarquia polinomial (ou seja, NP e co-NP) está em PP, e que . Também sabemos pelo Teorema de Toda que .$PP \subseteq PSPACE$$PH \subseteq P^{PP}$

Sabemos se ? Caso contrário, por que com um oráculo é mais forte que ? É possível que e PP \ nsubseteq PH ?P P P $PH \subseteq PP$$P$$PP$$PP$P P ⊈ P $PH \nsubseteq PP$$PP \nsubseteq PH$

Esta pergunta é muito simples, mas não encontrei nenhum recurso para resolvê-la.

Fiz essa pergunta relacionada, mas muito menos específica, ao estouro de matemática antes de aprender mais sobre o tópico.

Aqui está um pouco relacionado (mas diferente) pergunta: Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$ ?

Atualização: Dê uma olhada na pergunta de Noam Nisan aqui: Mais sobre PH em PP?

Huck, como Lance e Robin apontaram, temos oráculos em relação aos quais o PH não está no PP. Mas isso não responde à sua pergunta, que era a situação no mundo "real" (não relativizado)!

A resposta curta é que (como com tantas outras coisas na teoria da complexidade) não sabemos.

Mas a resposta mais longa é que existem boas razões para conjeturar que, de fato, PH ⊆ PP.

Primeiro, o teorema de Toda implica PH ⊆ BP.PP, em que BP.PP é a classe de complexidade que "é PP como BPP é P" (em outras palavras, PP onde você pode usar uma randomização para decidir qual computação MAJORITY você deseja executar). Segundo, sob hipóteses plausíveis de derandomização (semelhantes às que são conhecidas por implicar P = BPP, por Nisan-Wigderson, Impagliazzo-Wigderson, etc.), teríamos PP = BP.PP.

Adendo, para responder às suas outras perguntas:

(1) Eu diria que não temos uma intuição convincente sobre a questão de saber se PP = P ^PP . Sabemos, pelos resultados de Beigel-Reingold-Spielman e Fortnow-Reingold, que o PP é fechado sob reduções não - adaptativas (tabela da verdade). Em outras palavras, uma máquina P que pode fazer consultas paralelas a um oráculo PP não é mais poderosa que o próprio PP. Mas o fato de esses resultados serem completamente quebrados para consultas adaptativas (não paralelas) ao oráculo do PP sugere que talvez os últimos sejam realmente mais poderosos.

(2) Da mesma forma, NP ^PP e coNP ^PP podem ser ainda mais poderosos que P ^PP . E PP O ^PP pode ser ainda mais poderoso e assim por diante. A sequência P, PP, P ^PP , PP ^PP , P ^{PP ^ PP} , etc. é chamada hierarquia de contagem e, assim como as pessoas conjecturam que o PH é infinito, também se pode conjecturar (embora talvez com menos confiança!) Que CH é infinito. Isso está intimamente relacionado à crença de que, em circuitos de limiar de profundidade constante (ou seja, redes neurais), adicionar mais camadas de portas de limiar fornece a você mais poder computacional.

Richard Beigel tem um oráculo em relação ao qual não está contido no PP.$P^{NP}$

Vereshchagin [Ver] mostrou que existe um oráculo em relação ao qual AM não está contido no PP. (Este resultado parece incomparável com o resultado vs PP.)$P^{NP}$

[Ver] NK Vereshchagin. Sobre o poder da PP , Proceedings of IEEE Complexity'92, pp. 138-143, 1992.

Algo que não foi mencionado até agora (tanto quanto eu posso ver) e que se mantém no mundo não relativizado é o seguinte:

Isso foi observado por Vyalyi neste artigo e deriva do fortalecimento de dois teoremas:

1. Teorema de Toda - Vyalyi mostra que uma consulta a um oráculo é suficiente para uma " máquina " simular o .P P $\sharp P$$P$$PH$
2. A inclusão comprovada por Kitaev e Watrous. Vyalyi prova que o também está no , uma classe que está contida no .Q M A A 0 P P P $QMA \subseteq PP$$QMA$$A_0PP$$PP$