¿Es

37

Sabemos que el primer nivel de la jerarquía polinómica (es decir, NP y co-NP) está en PP, y que . También sabemos por el teorema de Toda que . $PP \subseteq PSPACE$ $PH \subseteq P^{PP}$

¿Sabemos si ? Si no, ¿por qué es que con un oráculo de es más fuerte que ? ¿Es posible que y ? $PH \subseteq PP$ $P$ $PP$ $PP$ $PH \nsubseteq PP$ $PP \nsubseteq PH$

Esta pregunta es muy simple, pero no he encontrado ningún recurso para abordarla.

Hice esta pregunta relacionada pero mucho menos específica sobre el desbordamiento matemático antes de aprender más sobre el tema.

Aquí hay una pregunta algo relacionada (pero diferente): ¿es ? $coNP^{\#P}=NP^{\#P}=P^{\#P}$

Actualización: Eche un vistazo a la pregunta de Noam Nisan aquí: ¿ Más información sobre PH en PP?

cc.complexity-theory counting-complexity polynomial-hierarchy Huck Bennett
fuente

37

Huck, como señalaron Lance y Robin, tenemos oráculos en relación con los cuales el PH no está en PP. Pero eso no responde a su pregunta, ¡cuál era la situación en el mundo "real" (no relativizado)!

La respuesta corta es que (como con mucho más en la teoría de la complejidad) no lo sabemos.

Pero la respuesta más larga es que hay muy buenas razones para conjeturar que efectivamente PH ⊆ PP.

Primero, el teorema de Toda implica PH ⊆ BP.PP, donde BP.PP es la clase de complejidad que "es a PP como BPP es a P" (en otras palabras, PP donde puede usar una aleatorización para decidir qué cálculo de MAYORÍA desea realizar). En segundo lugar, bajo hipótesis de deslealización plausibles (similares a las que se sabe que implican P = BPP, de Nisan-Wigderson, Impagliazzo-Wigderson, etc.), tendríamos PP = BP.PP.

Anexo, para abordar sus otras preguntas:

(1) Diría que no tenemos una intuición convincente sobre la cuestión de si PP = P ^PP . Sabemos, por los resultados de Beigel-Reingold-Spielman y Fortnow-Reingold, que el PP está cerrado bajo reducciones no adaptativas (tabla de verdad). En otras palabras, una máquina P que puede realizar consultas paralelas a un oráculo PP no es más poderosa que el propio PP. Pero el hecho de que estos resultados se desglosen por completo para consultas adaptativas (no paralelas) al oráculo PP sugiere que tal vez estos últimos sean realmente más poderosos.

(2) Del mismo modo, NP ^PP y coNP ^PP podrían ser aún más potentes que P ^PP . Y PP ^PP podría ser aún más poderoso, y así sucesivamente. La secuencia P, PP, P ^PP , PP ^PP , P ^{PP ^ PP} , etc. se llama jerarquía de conteo , y así como las personas conjeturan que PH es infinito, también se puede conjeturar (¡aunque tal vez con menos confianza!) Que CH es infinito. Esto está estrechamente relacionado con la creencia de que, en los circuitos de umbral de profundidad constante (es decir, las redes neuronales), agregar más capas de puertas de umbral le da más potencia de cálculo.

Scott Aaronson
fuente

77

Scott, estoy un poco confundido por la afirmación de que el PP "plausiblemente" contendrá PH. La primera separación de PH de PP a través de oráculos tiene en su núcleo combinatorio la separación original de Minski y Papert que un AND-de-OR no puede ser simulado por una puerta de umbral de grado polylog. Creo que la versión no uniforme de Toda está simulando AC0 mediante una distribución de probabilidad sobre las puertas de umbral de polylog-degree que obtiene la respuesta correcta whp. Por lo tanto, en el nivel no uniforme, la compuerta "BP" agrega una potencia significativa, a diferencia de P no uniforme frente a BPP o NP frente a AM. Entonces, por ejemplo, ¿PH en PP con un oráculo aleatorio?

Noam

Noam, ¿los PP con un oráculo aleatorio no contienen BP.PP? (No veo por qué no debería). Si es así, entonces seguro que el PH está en PP con un oráculo aleatorio. Pero permítanme hacer otra pregunta: ¿hay alguna clase de complejidad C para la cual tengamos buenas razones para creer que C no es igual a BP.C?

Scott Aaronson

Necesitaría amplificación para mostrar que PP = BP.PP con un oráculo aleatorio; no veo cómo hacerlo. Incluso de manera no uniforme, no puedo ver que el PH esté en PP / poli. ¿No parece que el AND-of-ORs en el umbral de polylog-degree-sugiere que incluso el PH no uniforme no está en PP?

Noam

Aquí hay un artículo que muestra BP.PP = PP bajo una hipótesis plausible: www.cs.uwyo.edu/~jhitchco/papers/hhdcc.ps

Scott Aaronson

8

Lo que me faltaba era que Fortnow y Reingold demostraron que el PP está cerrado bajo reducciones verificables, un cierre que es necesario para la aleatorización utilizando un PRG (o de manera no uniforme o con un oráculo aleatorio). Sin embargo, todavía estoy perplejo aquí, y formulé una pregunta al respecto: cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp

Noam

23

Richard Beigel tiene un oráculo con respecto al cual no está contenido en PP. $P^{NP}$

Lance Fortnow
fuente

20

Vereshchagin [Ver] mostró que hay un oráculo en relación con el cual AM no está contenido en PP. (Este resultado parece incomparable con el resultado vs PP). $P^{NP}$

[Ver] NK Vereshchagin. Sobre el poder del PP , Actas de IEEE Complexity'92, pp. 138-143, 1992.

Robin Kothari
fuente

13

Algo que no se ha mencionado hasta ahora (hasta donde puedo ver) y que se mantiene en el mundo no relativizado es el siguiente:

P H \subseteq P P if Q M A = P P .

$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$

Esto fue observado por Vyalyi en este artículo y proviene del fortalecimiento de dos teoremas:

$\sharp P$ $P$ $PH$
$QMA \subseteq PP$ $QMA$ $A_0PP$ $PP$

Alessandro Cosentino
fuente

¿Es

Respuestas: