Plus sur le PH en PP?

Une question récente de Huck Bennett demandant si la classe PH était contenue dans la classe PP, a reçu des réponses quelque peu contradictoires (tout à fait vrai, semble-t-il). D'un côté, plusieurs résultats Oracle ont été donnés, et de l'autre Scott a suggéré que la réponse était probablement positive puisque le théorème de Toda montre que PH est dans BP.PP, la variante probabiliste de PP, et nous pensons généralement que la randomisation par exemple, des hypothèses de dureté raisonnable impliquent des PRG pouvant remplacer la randomisation.

Maintenant, dans le cas de PP, il n'est pas évident a priori que même un PRG "parfait" impliquera une dérandomisation complète puisque la dérandomisation naturelle exécuterait l'algorithme d'origine avec la sortie du PRG pour toutes les semences possibles polynomiales et prendrait un vote majoritaire. . Il n’est pas clair que l’adoption de ce vote à la majorité parmi les calculs de PP est une chose qui peut être faite dans PP même. Cependant, un article de Fortnow et Reingold montre que PP est fermé en raison de réductions du nombre de tables de vérité (prolongeant le résultat surprenant selon lequel PP est fermé en intersection), ce qui semble suffisant pour prendre ce vote majoritaire.

Alors, quelle est la question ici? Toda, Fortnow-Reingold et tous les processus de dénormalisation basés sur les PRG semblent tous relativiser, ce qui impliquerait donc que PH soit en PP pour chaque oracle pour lequel des PRG appropriés existent. Ainsi, pour tous les oracles sous lesquels le PP ne contient pas de PH (par exemple de Minski & Papert, de Beigel ou de Vereshchagin ), les PRG pour le PP n'existent pas. Cela implique notamment que pour ces oracles, il n’existe pas de fonctions suffisamment dures dans EXP (sinon, des PRG de type NW-IW existeraient). En regardant le côté positif, cela impliquerait que quelque part dans chacun de ces résultats oracle se cache un algorithme PP (non uniforme) pour (approximer) EXP avec cet oracle. C'est étrange puisque tous ces résultats Oracle semblent reposer sur de nouvelles limites inférieures de PP.(pour les circuits à seuil) et sont simples dans leurs machines de construction d’oracles, donc je ne vois pas où se cache une limite supérieure pour le PP. Peut-être que cette limite supérieure fonctionnerait en général en montrant que -PP (non uniforme) peut calculer (ou au moins biaiser) sur la totalité de l'EXP? Quelque chose comme ça ne donnerait-il pas au moins une simulation CH d’EXP?

Donc, je suppose que ma question est double: (1) cette chaîne de raisonnement a-t-elle un sens? (2) Si oui, alors quelqu'un peut-il "découvrir" les bornes supérieures implicites pour PP?

Edit par Aaron Sterling: le placer sur la première page et ajouter une prime. C’était une de mes questions préférées et elle n’a toujours pas de réponse.

cc.complexity-theory counting-complexity derandomization relativization Noam
la source

En effet, commencez par une fonction booléenne dans AC0 qui ne peut pas être calculée par une porte de seuil polylog (N). Pour chaque oracle nous définissons le langage (où est les bits de la ième tranche de ). Depuis , , pour tous . La ième étape de diagonalisation choisira (pour certains ) de sorte que le ième PP TM se trompe sur, ce qui se passe depuis

f : {0, 1}^{N} \to {0, 1}

$f:\{0,1\}^N \rightarrow \{ 0,1\}$

A

$A$

L_{A} = {1^{n} | f (A_{n}) = 1}

$L_A= \{1^n | f(A_n)=1\}$

A_{n}

$A_n$

2^{n}

$2^n$

n

$n$

A

$A$

f \in A C 0

$f \in AC0$

L_{A} \in P H^{A}

$L_A \in PH^A$

A

$A$

t

$t$

A_{n}

$A_n$

n

$n$

t

$t$

1^{n} \in L_{A} ?

$1^n \in L_A?$

f

$f$ n'est pas polylog (N) -threshold (comme le calcul d'une machine PP). Alors . Mais peut-être que ...

L_{A} \notin P P^{A}

$L_A \not\in PP^A$

L_{A} \in P P^{A} | p o l y

$L_A \in PP^A|poly$

Noam

Donc, pour obtenir aussi nous aurions besoin de compresser plusieurs instances de dans une seule longueur . Cela semble facilement faisable en définissant , où , pour une chaîne bits , désigne le -bits décrivant si pour toutes possibles « s de longueur . Mais il faudrait améliorer la limite inférieure de pour exiger que copies de sur différents

L_{A} \notin P P^{A} / p o l y

$L_A \not\in PP^A/poly$

f

$f$

n

$n$

L_{A} = {x | f (A_{x}) = 1}

$L_A = \{ x | f(A_x)=1\}$

n

$n$

x

$x$

A_{x}

$A_x$

2^{n}

$2^n$

x y \in A

$xy \in A$

2^{n}

$2^n$

y

$y$

n

$n$

f

$f$

N

$N$

f

$f$

N

$N$ Les chaînes à bits ne peuvent pas être calculées par les portes à seuil polylog (N), même avec les bits d'aide polylog (N). Cela devrait donc être faux pour tout . Une limite supérieure intéressante semble-t-il.

f \in A C 0

$f \in AC0$

Noam

À bien y penser, le constat que sous chaque oracle qui fabrique PH / PP, il n’existe aucun PRG efficace qui trompe les algorithmes de BP.PP ne devrait pas être plus surprenant que le fait que sous chaque oracle qui fabrique BPP / ⊆ P, il y en a pas de PRG efficaces qui trompent les algorithmes BPP. En effet, chaque oracle qui fabrique PH / ⊆ PP fabrique également BP.PP / PP selon le théorème de Toda (relativisé). Mais peut-être que je manque le point. -

slimton

C'est un bon point. Cependant, intuitivement, lorsque vous créez un oracle pour lequel le cœur de la construction confère un pouvoir inhabituel à , de sorte que cela implique également un pouvoir inhabituel pour et rend ainsi les PRG impossibles. . L'oracle pour ne semble pas donner un pouvoir inhabituel de (ou à une classe) , mais plutôt de limiter la puissance du . Je ne suis toutefois pas sûr que cette différence puisse être formalisée d'une manière ou d'une autre.

P^{A} \neq B P P^{A}

$P^A \ne BPP^A$

B P P^{A}

$BPP^A$

P^{A} / p o l y

$P^A/poly$

P H^{A} ⊈ P P^{A}

$PH^A \not\subseteq PP^A$

P^{A}

$P^A$

P P^{A}

$PP^A$

Noam

Comme je l’ai fait remarquer plus haut: dans les constructions pour le cœur de la construction consiste à donner un pouvoir "non naturel" à BPP (et donc également à P / poly), par exemple en installant de nombreux témoins du dur oracle dans des endroits où: seule la randomisation peut les trouver. Il est donc intéressant de noter que ce pouvoir est suffisant pour les problèmes "généraux", du moins le pouvoir inattendu de P / poly est clair. D'autre part, je ne vois nulle part que l'oracle permettant de séparer le PH du PP donne un pouvoir non naturel à P / Poly ou à une autre classe, en fait. Je ne suis pas sûr que cette différence soit "réelle" cependant.

P \neq B P P

$P \ne BPP$

Noam

Plus sur le PH en PP?

Réponses: