¿

Supongamos que . Entonces demuestra un sencillo argumento de que . ¿Podemos ir un paso más allá y obtener ? El argumento simple es $NP=PP$ $PH^{PP}=NP$ $PP^{PP}=NP$

Teorema Si entonces . $NP=PP$ $PH^{PP}=NP$

Prueba es cerrado bajo complemento (debido a Gill), por lo que . Tome cualquier nivel de : entonces . $PP$ $NP=coNP=PH$ $PH^{PP}$ $\Sigma_i^{P^{PP}}=\Sigma_i^{P^{NP}}=\Sigma_{i+1}^{P}=NP$ $\square$

Una manera plausible de llegar a la consecuencia deseada es observar que en este mundo, el protocolo de prueba interactivo para el se ha desrandomizado y desmerlinizado hasta el punto en que un mensaje a Arthur tiene una integridad y solidez perfectas (como bajo la hipótesis). Si puede explotar este hecho y calcular el permanente en alguna clase que sea baja para , como o o , ya hemos terminado. Eso nos daría $\textsf{Permanent}$ $NP=P^{\#P}$ $PP$ $UP$ $BQP$ $SPP$ (por ejemplo), lo que daría inmediatamente . $NP=PP\implies PP=UP$ $PP^{PP}=PP^{UP}=PP=NP$

(Esto surgió en mi tesis, donde investigo la hipótesis , y también surgió al tratar de arreglar el teorema roto de Scott Aaronson $QMA=PP$ , el teorema 5 en los oráculos es sutil pero no malicioso). $PP\subset BQP_{/qpoly}\implies CH=PP=QMA$

cc.complexity-theory counting-complexity conditional-results Lieuwe Vinkhuijzen
fuente

@ EmilJeřábek Se podría pensar que

sería bajo para

, ya que

es bajo para

, pero no, eso no se sabe. Se sabe que las clases

son bajas para

y son incomparables hasta donde se sabe. Entonces la clase

es algo así como baja para

, es decir,

N P

$NP$

P P

$PP$

N P \cap c o N P

$NP\cap coNP$

N P

$NP$

N P \subseteq P P

$NP\subseteq PP$

S P P

$SPP$

B Q P

$BQP$

P P

$PP$

\oplus P

$\oplus P$

P P

$PP$

, así que si usted dio unalgoritmo

para el permanente bajo esta hipótesis, eso también nos da nuestro colapso deseado.

P P^{\oplus P} \subseteq P^{P P}

$PP^{\oplus P}\subseteq P^{PP}$

\oplus P

$\oplus P$

Lieuwe Vinkhuijzen

Me acordé un poco: NP no se sabe que sea bajo para el propio PP, pero es bajo para P ^ PP, que es lo suficientemente bueno como para llegar a la conclusión.

Emil Jeřábek

Tenemos por lo tanto por el supuesto, como bajo el supuesto, NP cerrado bajo complemento. Esto implica .

P P^{N P} \subseteq P P^{M o d P H} \subseteq P^{P P},

$\mathrm{PP^{NP}\subseteq PP^{ModPH}\subseteq P^{PP}},$

P P^{P P} \subseteq P P^{N P} \subseteq P^{P P} \subseteq P^{N P} \subseteq N P

$\mathrm{PP^{PP}\subseteq PP^{NP}\subseteq P^{PP}\subseteq P^{NP}\subseteq NP}$

C H = N P

$\mathrm{CH=NP}$

Emil Jeřábek
fuente

P^{P P}

$P^{PP}$

M o d P H

$ModPH$

\exists

$\exists$

\forall

$\forall$

{M o d}_{m}

$\mathrm{Mod}_m$

m

$m$

{M o d}_{m} P

$\mathrm{Mod}_m\mathrm P$

P P \subseteq M o d P H ⟹ C H = P^{P P} = M o d P H

$\mathrm{PP\subseteq ModPH\implies CH=P^{PP}=ModPH}$

P P^{B P P^{A}} \subseteq P P^{A}

$PP^{BPP^A} \subseteq PP^A$

A

$A$

P P^{\oplus P} \subseteq P^{P P}

$PP^{\oplus P} \subseteq P^{PP}$

P P^{N P} \subseteq P P^{B P P^{\oplus P}} \subseteq P P^{\oplus P} \subseteq P^{P P}

$PP^{NP} \subseteq PP^{BPP^{\oplus P}} \subseteq PP^{\oplus P} \subseteq P^{PP}$

Sí, por supuesto. Lee los comentarios anteriores.

Emil Jeřábek

¿

Respuestas: