Est-ce que ?

Nous savons que le premier niveau de la hiérarchie polynomiale (c'est-à-dire NP et co-NP) est en PP, et que . Le théorème de Toda indique également que .$PP \subseteq PSPACE$$PH \subseteq P^{PP}$

Savons-nous si ? Si non, pourquoi est-ce que avec un oracle en est plus fort que le ? Est-il possible que et PP \ nsubseteq PH ?$PH \subseteq PP$$P$$PP$$PP$$PH \nsubseteq PP$$PP \nsubseteq PH$

Cette question est très simple, mais je n'ai trouvé aucune ressource pour y répondre.

J'ai posé cette question connexe mais beaucoup moins spécifique sur le dépassement en maths avant d'en apprendre davantage sur le sujet.

Voici une question quelque peu connexe (mais différente): Est-ce que $coNP^{\#P}=NP^{\#P}=P^{\#P}$ ?

Mise à jour: Jetez un coup d'œil à la question de Noam Nisan ici: Plus d'informations sur le PH en PP?

Huck, comme l'ont souligné Lance et Robin, nous avons des oracles par rapport auxquels le PH n'est pas en PP. Mais cela ne répond pas à votre question: quelle était la situation dans le "vrai" monde (non relativisé)!

La réponse courte est que (comme c'est souvent le cas dans la théorie de la complexité), nous ne le savons pas.

Mais la réponse la plus longue est qu’il existe de très bonnes raisons de supposer qu’en réalité, PH ⊆ PP.

Premièrement, le théorème de Toda implique PH ⊆ BP.PP, où BP.PP est la classe de complexité qui "est de PP comme BPP est de P" (en d'autres termes, PP où vous pouvez utiliser une randomisation pour décider quel calcul MAJORITY vous voulez. effectuer). Deuxièmement, dans des hypothèses de dérandomisation plausibles (similaires à celles connues pour impliquer P = BPP, de Nisan-Wigderson, Impagliazzo-Wigderson, etc.), nous aurions PP = BP.PP.

Addendum, pour répondre à vos autres questions:

(1) Je dirais que nous n’avons pas d’intuition convaincante de toute façon sur la question de savoir si PP = P ^PP . Nous savons, d'après les résultats de Beigel-Reingold-Spielman et de Fortnow-Reingold, que PP est fermé en raison de réductions non adaptatives (table de vérité). En d'autres termes, une machine P capable d'effectuer des requêtes parallèles vers un oracle PP n'est pas plus puissante que PP elle-même. Cependant, le fait que ces résultats soient complètement décomposés pour les requêtes adaptatives (non parallèles) à l’oracle PP suggère que ces derniers sont peut-être vraiment plus puissants.

(2) De même, NP ^PP et coNP ^PP pourraient être encore plus puissants que P ^PP . Et PP ^PP pourrait être encore plus puissant, et ainsi de suite. La séquence P, PP, PP, ^PP , PP, ^PP , ^PP , etc. est appelée hiérarchie de comptage , et de la même façon que les gens supposent que le PH est infini, on peut aussi conjecturer (bien que peut-être avec moins de confiance!) Que CH est infini. Cela est étroitement lié à la conviction selon laquelle, dans les circuits à seuil à profondeur constante (c.-à-d. Les réseaux de neurones), l'ajout de plusieurs couches de portes à seuil donne plus de puissance de calcul.

Richard Beigel a un oracle par rapport auquel n'est pas contenu dans PP.$P^{NP}$

Vereshchagin [Ver] a montré qu'il existe un oracle par rapport auquel AM n'est pas contenu dans PP. (Ce résultat semble incomparable avec le résultat vs PP.)$P^{NP}$

[Ver] NK Vereshchagin. On the power of PP , Actes de IEEE Complexity'92, p. 138-143, 1992.

Quelque chose qui n'a pas été mentionné jusqu'à présent (pour autant que je sache) et qui est valable dans le monde non relativisé est le suivant:

Ceci a été observé par Vyalyi dans cet article et provient du renforcement de deux théorèmes:

1. Le théorème de Toda - Vyalyi montre qu'une requête sur un oracle est suffisante pour qu'une " machine " simule .$\sharp P$$P$$PH$
2. L'inclusion prouvée par Kitaev et Watrous. Vyalyi prouve que est également dans , une classe contenue dans .$QMA \subseteq PP$$QMA$$A_0PP$$PP$