Est-ce que ?

37

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 .PPPSPACEPHPPP

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 ?PHPPPPPPPPHPPPPPH

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 Bennett
la source

Réponses:

37

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.

Scott Aaronson
la source
7
Scott, je suis un peu dérouté par l'affirmation selon laquelle "plausiblement" PP contiendra du PH. La première séparation de PH de PP via des oracles a pour noyau combinatoire la séparation de Minski & Papert originale selon laquelle un AND-of-ORs ne peut pas être simulé par une porte de seuil de polylog. Je pense que la version non uniforme de Toda simule AC0 par une distribution de probabilité sur des portes de seuil en polylog, ce qui donne la réponse correcte whp. Ainsi, au niveau non uniforme, la porte "BP" ajoute une puissance significative, contrairement à P non vs uniforme ou à NP vs AM. Ainsi, par exemple, PH est-il en PP avec un oracle aléatoire?
Noam
Noam, est-ce que PP avec un oracle aléatoire ne contient pas BP.PP? (Je ne vois pas pourquoi cela ne devrait pas.) Si c'est le cas, alors que PH est en PP avec oracle aléatoire. Mais permettez-moi de poser une autre question: existe-t-il une classe de complexité C pour laquelle nous avons de bonnes raisons de croire que C n’est pas égal à BP.C?
Scott Aaronson
Vous auriez besoin d'une amplification pour montrer que PP = BP.PP avec un oracle aléatoire - je ne vois pas comment faire cela. Même de manière non uniforme, je ne vois pas que PH est en PP / poly. Les AND-of-ORs ne figurant pas dans le polylog-seuil-degré ne sembleraient-ils pas suggérer que même si le pH n'est pas uniformément uniforme, il ne l'est pas en PP?
Noam
Voici un article qui montre BP.PP = PP sous une hypothèse plausible: www.cs.uwyo.edu/~jhitchco/papers/hhdcc.ps
Scott Aaronson
8
Ce qui me manquait, c’est que Fortnow et Reingold ont montré que PP est fermé en raison de réductions de table de vérité, une fermeture nécessaire pour la dérandomisation à l’aide d’une PRG (ou non uniformément ou avec un oracle aléatoire). Cependant, je suis toujours perplexe ici et ai formulé une question à ce sujet: cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp
Noam
23

Richard Beigel a un oracle par rapport auquel n'est pas contenu dans PP.PNP

Lance Fortnow
la source
20

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.)PNP

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

Robin Kothari
la source
13

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:

PHPP if QMA=PP.

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 .PPPH
  2. L'inclusion prouvée par Kitaev et Watrous. Vyalyi prouve que est également dans , une classe contenue dans .QMAPPQMAA0PPPP
Alessandro Cosentino
la source