Apakah

Misalkan . Kemudian argumen sederhana menunjukkan bahwa . Bisakah kita melangkah lebih jauh dan mendapatkan ? Argumen sederhananya adalah $NP=PP$ $PH^{PP}=NP$ $PP^{PP}=NP$

Teorema Jika maka . $NP=PP$ $PH^{PP}=NP$

Bukti ditutup di bawah pelengkap (karena Gill), sehingga . Ambil setiap tingkat : maka . $PP$ $NP=coNP=PH$ $PH^{PP}$ $\Sigma_i^{P^{PP}}=\Sigma_i^{P^{NP}}=\Sigma_{i+1}^{P}=NP$ $\square$

Salah satu cara yang masuk akal-mencari untuk mendapatkan konsekuensi yang diinginkan adalah dengan mengamati bahwa di dunia ini, protokol bukti interaktif untuk telah derandomized dan de-Merlinized ke titik di mana salah satu pesan ke Arthur memiliki kelengkapan sempurna dan kesehatan (sebagai bawah hipotesis). Jika Anda dapat memanfaatkan fakta ini dan menghitung Tetap di beberapa kelas yang rendah untuk , seperti atau atau , kita sudah selesai. Itu akan memberi kita $\textsf{Permanent}$ $NP=P^{\#P}$ $PP$ $UP$ $BQP$ $SPP$ (misalnya), yang akan segera memberikan . $NP=PP\implies PP=UP$ $PP^{PP}=PP^{UP}=PP=NP$

(Ini muncul dalam tesis saya, di mana saya menyelidiki hipotesis , dan itu juga datang ketika mencoba untuk memperbaiki Scott Aaronson teorema rusak $QMA=PP$ , Teorema 5 di Oracle yang Halus tapi tidak berbahaya). $PP\subset BQP_{/qpoly}\implies CH=PP=QMA$

cc.complexity-theory counting-complexity conditional-results Pengganti Vinkhuijzen
sumber

@ EmilJeřábek Anda akan berpikir bahwa

akan rendah untuk

, karena

rendah untuk

dan

, tetapi tidak, itu tidak diketahui. Kelas-kelas

dan

diketahui rendah untuk

, dan tidak ada bandingannya sejauh yang diketahui orang. Maka kelas

adalah sesuatu yang rendah untuk

, yaitu

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$

, jadi jika Anda memberikan

-algoritma untuk Permanen di bawah hipotesis ini, itu memberi kita keruntuhan yang kita inginkan juga.

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

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

\oplus P

$\oplus P$

Lieuwe Vinkhuijzen

Saya sedikit salah ingat: NP tidak diketahui rendah untuk PP itu sendiri, tetapi rendah untuk P ^ PP, yang cukup baik untuk mendapatkan kesimpulan.

Emil Jeřábek

Kami memiliki dengan demikian dengan asumsi, seperti di bawah asumsi, NP ditutup di bawah pelengkap. Ini berarti .

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
sumber

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

Ya tentu saja. Baca komentar di atas.

Emil Jeřábek

Apakah

Jawaban: