¿Más sobre PH en PP?

Una pregunta reciente de Huck Bennett sobre si la clase PH estaba contenida en la clase PP, recibió respuestas algo contradictorias (todo es cierto, parece). Por un lado, se dieron varios resultados de oráculo en sentido contrario, y por otro Scott sugirió que la respuesta es probablemente positiva ya que el teorema de Toda muestra que PH está en BP.PP, la variante probabilística de PP, y generalmente creemos que la aleatorización sí no ayuda mucho, por ejemplo, los supuestos de dureza razonables implican PRG que pueden reemplazar la aleatorización.

Ahora, en el caso de PP, no está claro a priori que incluso un PRG "perfecto" implicará una desrandomización completa ya que la desrandomización natural ejecutaría el algoritmo original con la salida del PRG para todas las semillas polinomialmente posibles y tendría un voto mayoritario . No está claro que tomar ese voto mayoritario entre los cálculos de PP es algo que se puede hacer en el propio PP. Sin embargo, un documento de Fortnow y Reingold muestra que el PP está cerrado bajo las reducciones de la tabla de verdad (extendiendo el sorprendente resultado de que el PP está cerrado bajo la intersección), lo que parece ser suficiente para tomar este voto mayoritario.

Entonces, ¿cuál es la pregunta aquí? Toda, Fortnow-Reingold y todas las desviaciones aleatorias basadas en PRG, parecen relativizarse, por lo que implicaría ese PH en PP para cada oráculo para el que existen PRG apropiadas. Entonces, para todos los oráculos bajo los cuales PP no contiene PH (por ejemplo, de Minski & Papert, de Beigel o de Vereshchagin ), los PRG para PP no existen. En particular, esto implica que para estos oráculos no hay funciones apropiadamente difíciles en EXP (de lo contrario, existirían PRG similares a NW-IW). Mirando el lado positivo, esto implicaría que en algún lugar dentro de cada uno de estos resultados de oráculo se esconde un algoritmo PP (no uniforme) para EXP (aproximado) con ese oráculo. Esto es extraño ya que todos estos resultados de oráculo parecen depender de nuevos límites inferiores de PP(para circuitos de umbral) y son sencillos en su maquinaria de construcción de oráculo, por lo que no veo dónde se esconde un límite superior para PP. ¿Quizás este límite superior funcionaría en general mostrando que (no uniforme) -PP puede calcular (o al menos dar un sesgo) a todo EXP? ¿Algo así no daría al menos una simulación CH de EXP?

Entonces, supongo que mi pregunta es doble: (1) ¿tiene sentido esta cadena de razonamiento? (2) Si es así, ¿alguien puede "descubrir" los límites superiores implícitos para PP?

Editar por Aaron Sterling: colocando esto en la portada y agregando una recompensa. Esta fue una de mis preguntas favoritas, y todavía no tiene respuestas.

cc.complexity-theory counting-complexity derandomization relativization Noam
fuente

De hecho, comience con una función booleana

en AC0 que no puede ser calculada por una puerta de umbral de polylog (N) -gree. Para cada oráculo

definimos el lenguaje

(donde

es el

bits de la

'th rebanada de

). Desde

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$

, para todos

. Elpaso de diagonalización

'elegirá

(para algunos

) de modo que el

' th PP TM cometa un error en

, lo que sucede ya que

no es el umbral polylog (N) (como lo es el cálculo de una máquina PP). Así

. Pero tal vez

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$

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

Entonces, para obtener también

tendríamos que agrupar muchas instancias de

en una sola longitud

. Esto parece fácilmente factible definiendo

, donde para una cadena de

bits

denota los

bits que describen si

para los

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$

posibles

de longitud

. Pero nos lo necesario para mejorar el límite inferior de

exigir que

copias de

en diferentes

cuerdas -bit no se pueden calcular por polylog bits de ayuda (N) -Grado puertas de umbral, incluso con polylog (N). Entonces esto debería ser falso para cualquier

. Parece un límite superior interesante.

2^{n}

$2^n$

y

$y$

n

$n$

f

$f$

N

$N$

f

$f$

N

$N$

f \in A C 0

$f \in AC0$

Noam

Ahora que lo pienso, la observación de que bajo cada oráculo que hace PH / ⊆ PP no hay PRG eficientes que engañen a los algoritmos BP.PP no debería ser más sorprendente que el hecho de que bajo cada oráculo que hace BPP / ⊆ P hay no hay PRG eficientes que engañen a los algoritmos BPP. Esto se debe a que cada oráculo que produce PH / ⊆ PP también produce BP.PP / ⊆ PP según el teorema de Toda (relativizado). Pero tal vez me estoy perdiendo el punto. -

slimton

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

Como señalé anteriormente: en las construcciones para el quid de la construcción está dando poder "no natural" a BPP (y, por lo tanto, también a P / poly), por ejemplo, plantando muchos testigos del oráculo duro en lugares donde solo la aleatorización puede encontrarlos. Entonces, si bien es interesante que este poder sea suficiente para problemas "generales", al menos el poder inesperado de P / poly es claro. Por otro lado, no puedo ver en ninguna parte que el oráculo para separar el PH del PP le dé un poder no natural a P / poly o cualquier otra clase, de hecho. Sin embargo, no estoy seguro de que esta diferencia sea "real".

P \neq B P P

$P \ne BPP$

Noam

¿Más sobre PH en PP?

Respuestas: