Runtuh dengan asumsi bahwa

Diketahui bahwa jika $NP\subseteq P/Poly$ maka hierarki polinomial runtuh menjadi dan .$\Sigma_2^{P}$$MA = AM$

Apa keruntuhan terkuat yang diketahui terjadi jika ?$NEXP\subseteq P/Poly$

Saya percaya yang terkuat adalah . Ini dibuktikan oleh Impagliazzo Kabanets dan Wigderson.$NEXP = MA$

Lihat https://scholar.google.com/scholar?cluster=17275091615053693892&hl=id&as_sdt=0,5&sciodt=0,5

Saya juga tertarik mengetahui ada yang lebih kuat dari ini.

Sunting (8/24): OK, saya memikirkan beberapa kemungkinan runtuhnya yang lebih kuat, yang pada dasarnya mengikuti dari bukti-bukti dari kertas terkait di atas. Karena menyiratkan N E X P = E X P (lihat link di atas), dan E X P ditutup di bawah pelengkap, kami juga memiliki N E X P ditutup di bawah pelengkap dan karena itu N E X P = M A ∩ c o M $NEXP \subset P/poly$$NEXP = EXP$$EXP$$NEXP$$NEXP = MA \cap coMA$ , yang sedikit lebih kuat. Memang, hipotesis menyiratkan bahwa untuk setiap bahasa, satu tunggal saksi tali w $NEXP$$w_n$dapat digunakan dalam protokol MA yang sesuai untuk semua instance-YES dari panjang yang diberikan , demikian juga N $n$ (di mana O M A = "Oblivious MA", lihat Fortnow-Santhanam-mehttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&rep=rep1&type=pdf$NEXP = OMA \cap coOMA$$OMA$). Properti ekstra ini, meskipun bersifat teknis, dapat terbukti bermanfaat dalam beberapa argumen rangkaian batas bawah.

Sunting 2: Sepertinya Andrew Morgan sudah menyoroti ini. Aduh :)

Banyak hal menyenangkan terjadi. Sebagian besar yang saya tahu mulai dengan kertas IKW . Di sana, keruntuhan $\textrm{NEXP} = \textrm{MA}$ ditampilkan, dan (saya pikir) adalah keruntuhan literal terkuat dari kelas kompleksitas yang kita ketahui. Ada beberapa jenis "runtuh" ​​meskipun saya pikir harus ditunjukkan.

Yang paling penting, saya pikir, adalah properti "saksi ringkas universal" (juga dari makalah IKW). Untuk satu, itu memberi Anda alat dari mana banyak dari yang lain runtuh adalah konsekuensi langsung; untuk yang lain, sirkuit batas bawah terbaru (misalnya di sini dan di sini ) untuk $\textsf{NEXP}$ mengeksploitasi koneksi ini. Secara singkat, properti mengatakan bahwa, untuk setiap $\textsf{NEXP}$ bahasa $L$ , dan setiap $\textsf{NEXP}$ -Mesin $M$ memutuskan $L$ , setiap $x \in L$ memiliki ringkas dideskripsikan saksi menurut $M$ . Secara formal, ada polinomial $p$ tergantung pada$M$ sehingga untuk setiap$x \in L$ , ada sirkuit$C_x$adalah urutan pilihan nondeterministik untuk M yang mengarah pada penerimaan input x . ukuran$p(|x|)$ sehingga tabel kebenaran$C_x$$M$$x$

Kesederhanaan para saksi sangat berguna, karena Anda dapat dengan mudah mengembalikan banyak yang lain dari itu. Sebagai contoh, ini sepele mengikuti bahwa $\textsf{NEXP} = \textsf{coNEXP} = \textsf{EXP}$ . Sebagai contoh, misalkan $L$ adalah $\textsf{NEXP}$ melalui $\textsf{NEXP}$ -Mesin $M$ . Properti saksi ringkas mengatakan ada polinomial $p$ sehingga $M$ memiliki saksi ringkas ukuran $p$ . Kita kemudian dapat memutuskan $L$ dalam $\textsf{EXP}$ dengan, pada input $x$ , memaksa semua sirkuit ukuran paling banyak $p(|x|)$ , dan memeriksa apakah mereka menyandikan urutan pilihan yang mengarah ke$M$ menerima input$x$ . Anda dapat menggabungkan ini dengan (sebelumnya dikenal melalui bukti interaktif) hasil$\textsf{EXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{EXP} = \textsf{MA}$ untuk menyimpulkan$\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{NEXP} = \textsf{MA}$ .

Perlu ditekankan bahwa kita bisa memilih $M$ dan karenanya bentuk saksi. Misalnya, Anda dapat menyimpulkan dari " $\textsf{NEXP}$ memiliki saksi ringkas universal" bahwa $\textsf{NEXP} = \textsf{OMA} = \textsf{co-OMA}$ . Di sini $\textsf{OMA}$ adalah "lupa-MA", yang berarti bahwa ada Merlin jujur ​​yang hanya bergantung pada panjang input. Sangat mudah untuk melihat bahwa $\textsf{OMA} \subseteq \textsf{P}/\textrm{poly}$ , jadi pada dasarnya ini hanya memberikan bentuk normal untuk bagaimana bahasa $\textsf{NEXP}$ dihitung dalam $\textsf{P}/\textrm{poly}$ dengan asumsi bahwa $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$di tempat pertama. Inilah salah satu cara untuk melihat keruntuhan ke $\textsf{OMA}$ :

Untuk bahasa $L \in \mathsf{NEXP}$ diputuskan oleh mesin $M$ , membangun $\mathsf{NEXP}$ mesin $M'$ sebagai berikut. Lihat input $n$ bit sebagai angka $N$ antara $1$ dan $2^n$ . Untuk setiap $x$ panjang $n$ , tebak saksi $w_x$ dan jalankan $M(x,w_x)$ untuk memverifikasinya. $M'(N)$ menerima jika dan hanya jika $M$ menerima setidaknya$N$Nilai N dari$x$ . Tebakan disusun sedemikian rupa sehingga deskripsi singkat dari saksi bagi$M'$ adalah sirkuit$C$ yang menghitung peta$(x,i) \mapsto$ yang$i$ sedikit -th dari$w_x$ . Sekarang anggaplah bahwa$N$ adalah tepatnya jumlah string dalam$L$ panjangnya$n$ . Kemudian saksi ringkas untuk$M'$ pada input$N$ adalah sirkuit yang secara bersamaan menyandikansemuadari$M$ saksi 's untuk panjang-$n$ input. Khususnya, jika$M'$ memiliki saksi yang ringkas, maka semuasaksi$M$ dapat dijelaskan secara simultan oleh sirkuit yang sama.

Untuk menyelesaikan klaim, kami akan mengingat $\textsf{NEXP} = \textsf{PCP}[\textrm{poly}, \textrm{poly}]$ . Membiarkan $M$ menjadi mesin yang menebak PCP dan kemudian secara deterministik mensimulasikan verifier, paragraf di atas memberi tahu kita keberadaan PCP yang $\textsf{NEXP}$ secara ringkas dan ringkas untuk setiap bahasa di NEXP . Jadi sekarang untuk mendapatkan $\textsf{NEXP} = \textsf{OMA}$ , kami telah Merlin mengirim deskripsi singkat tentang PCP untuk semua input dari panjang input saat ini, yang dapat diperiksa oleh Arthur dengan hanya memasukkan inputnya dan kemudian menjalankan verifikasi PCP.

[Terima kasih kepada Cody Murray untuk menunjukkan trik menggunakan input untuk menghitung jumlah string dalam $L$ . Sebelumnya saya punya $M'$ menggunakannya jika $\mathsf{NEXP}\subseteq\mathsf{P/poly}$ maka $\mathsf{NEXP}=\mathsf{EXP}$ untuk menuliskan tabel kebenaran$L$ , tetapi strategi Cody lebih elegan.]

Sebagai catatan akhir, sementara secara teknis tersirat oleh $\textsf{NEXP}=\textsf{MA}$ , runtuhnya $\textsf{NEXP}=\textsf{PSPACE}$ memiliki implikasi menarik lainnya. Diketahui bahwa $\textsf{PSPACE}$ memiliki bahasa yang lengkap yang dapat direduksi sendiri ke bawah maupun direduksi sendiri secara acak. Biasanya, semua bahasa tersebut berada di dalam $\textsf{PSPACE}$ dan oleh karena itu kami tidak boleh berharap untuk mengatakan (tanpa syarat) bahwa $\textsf{NEXP}$ memiliki bahasa yang begitu lengkap selama kami berharap $\textsf{NEXP} \ne \textsf{PSPACE}$ . Namun, jika $\textsf{NEXP} = \textsf{PSPACE}$ , maka $\textsf{NEXP}$ melakukannya miliki bahasa yang lengkap. Pernyataan serupa (menggantikan $\textsf{NEXP}$ dengan $\textsf{EXP}$ ) digunakan oleh Impagliazzo dan Wigderson untuk menyimpulkan semacam "dikotomi derandomisasi" untuk $\textsf{BPP}$ sehubungan dengan $\textsf{EXP}$ , sehingga mungkin berguna dalam menemukan konsekuensi lain dari $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$ .