Faz

Suponha . Em seguida, uma simples mostra argumento que . Podemos dar um passo adiante e obter ? O argumento simples é $NP=PP$ $PH^{PP}=NP$ $PP^{PP}=NP$

Teorema Se então . $NP=PP$ $PH^{PP}=NP$

Prova é fechada sob complemento (devido a Gill), de modo . Tomar qualquer nível de : então . $PP$ $NP=coNP=PH$ $PH^{PP}$ $\Sigma_i^{P^{PP}}=\Sigma_i^{P^{NP}}=\Sigma_{i+1}^{P}=NP$ $\square$

Uma maneira plausível de obter a conseqüência desejada é observar que, neste mundo, o protocolo de prova interativa para o foi desaerizado e des Merlinizado até o ponto em que uma mensagem para Arthur tem perfeição e integridade perfeitas (como sob a hipótese). Se você pode explorar esse fato e calcular o Permanente em alguma classe baixa para , como ou ou , estamos prontos. Isso nos daria $\textsf{Permanent}$ $NP=P^{\#P}$ $PP$ $UP$ $BQP$ $SPP$ (por exemplo), o que imediatamente dão . $NP=PP\implies PP=UP$ $PP^{PP}=PP^{UP}=PP=NP$

(Este surgiu em minha tese, onde eu investigar a hipótese , e também surgiu quando tentando consertar teorema quebrado de Scott Aaronson $QMA=PP$ , Teorema 5 em Oráculos são subtil mas não suspeito). $PP\subset BQP_{/qpoly}\implies CH=PP=QMA$

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

@ EmilJeřábek Você pensaria que

seria baixo para

, já que

é baixo para

, mas não, isso não é conhecido. As classes

são conhecidas por serem baixas para

e são incomparáveis até onde se sabe. Então a classe

é algo como baixo para

, ou seja,

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$

, portanto, se vocêderumalgoritmo

para a Permanente sob essa hipótese, isso também nos dará o colapso desejado.

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

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

\oplus P

$\oplus P$

Lieuwe Vinkhuijzen

Eu me lembrei um pouco: NP não é conhecido por ser baixo para o próprio PP, mas é baixo para P ^ PP, o que é bom o suficiente para chegar à conclusão.

Emil Jerabek

Temos portanto pela suposição, como sob a suposição, NP fechado sob complemento. Isto 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
fonte

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}$

Sim, claro. Leia os comentários acima.

Emil Jerabek

Faz

Respostas: