Konsekuensi dari NP = PSPACE

Apa konsekuensi buruk NP = PSPACE? Saya terkejut saya tidak menemukan apa-apa tentang ini, mengingat bahwa kelas-kelas ini adalah yang paling terkenal.

Secara khusus, apakah akan ada konsekuensi pada kelas bawah?

Jika , ini akan menyiratkan:$\mathsf{NP} = \mathsf{PSPACE}$

• Artinya, menghitung solusi untuk masalah di N P akan polytime direduksi untuk menemukan solusi tunggal;$\mathsf{P^{\#P}} = \mathsf{NP}$
  $\mathsf{NP}$

• Yaitu, algoritma acak polinomial-waktu dengan probabilitas keberhasilan hampir mendekati 1/2 adalah polinomial-waktu yang dapat direduksi menjadi algoritma acak polinomial-waktu dengan kesalahan satu sisi, di mana instance YA diterima dengan probabilitas kecil sewenang-wenang;$\mathsf{PP} = \mathsf{NP}$
  

• Yaitu, untuk masalah apa pun yang dapat diverifikasi dalam waktu polinomial, pengacakan memberikan percepatan waktu polinomial terbaik (tetapi ini hanyalah akibat wajar dari hierarki polinomial-waktu runtuh);$\mathsf{MA} = \mathsf{NP}$
  

• Yaitu, setiap masalah yang dapat dipecahkan oleh komputer kuantum memiliki sertifikat yang mudah diverifikasi untuk jawabannya; ini akan menjadi hasil positif yang penting dalam filosofi mekanika kuantum, dan mungkin akan membantu upaya membangun komputer kuantum (untuk memverifikasi bahwa mereka melakukan apa yang seharusnya dilakukan).$\mathsf{BQP} \subseteq \mathsf{NP}$
  

Semua ini adalah karena containments kelas di sisi kiri di (meskipun kami juga memiliki B Q P ⊆ P P ).$\mathsf{PSPACE}$$\mathsf{BQP \subseteq PP}$

Satu titik yang telah secara implisit namun tidak disebutkan secara eksplisit belum adalah bahwa kita akan mendapatkan . Meskipun ini setara dengan P H yang runtuh menjadi N P , ia mengikuti langsung dari kenyataan bahwa P S P A C E ditutup dengan komplemen, yang sepele untuk dibuktikan.$\mathsf{NP} = \mathsf{coNP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{PSPACE}$

Saya pikir layak untuk ditunjukkan sendiri karena banyaknya konsekuensi mengejutkan yang dimilikinya: ada bukti singkat yang menyaksikan ketika grafik tidak 3-warna, * non- * Hamiltonian, ketika dua grafik adalah * non-* isomorfik, ..., dan (dalam beberapa hal lebih umum) bahwa ada beberapa sistem bukti Cook-Reckhow di mana setiap tautologi proposisional memiliki bukti sebesar polinomial.$\mathsf{NP} = \mathsf{coNP}$

Jika ${\bf NP} = {\bf PSPACE}$

1) Polinomial Hirarki akan runtuh .${\bf NP }$

2) Kita sekarang akan memiliki karena kita tahu bahwa P S P A C E ≠ N ${\bf NP } \not ={\bf NL}$${\bf PSPACE} \not = {\bf NL}$

---MEMPERBARUI---

3) Diketahui bahwa , di mana mereka adalah versi yang dibatasi ruang logaritmik dari N P , C = P dan P P masing-masing. Kemudian menurut definisi tidak ada kelas kompleksitas ini bisa sama N P dengan asumsi bahwa N P = P S P A C E .${\bf NL} \subseteq {\bf C_=L} \subseteq {\bf PL}$${\bf NP}$${\bf C_=P}$${\bf PP}$${\bf NP}$${\bf NP} = {\bf PSPACE}$

Selain hasil yang ditunjukkan dalam semua jawaban lain, ada satu yang melibatkan Sistem Bukti Interaktif (${\bf IP}$), itulah generalisasi ${\bf NP}$ tempat Verifier dan Prover bertukar pesan untuk mengenali bahasa.

Diketahui bahwa ${\bf IP = PSPACE}$, jadi jika ${\bf NP = PSPACE}$, artinya hanya satu pesan yang cukup! Bagi saya yang lebih mengesankan dari hasil ini adalah bahwa Verifier tidak perlu menantang Prover dan dapat mempercayai pesan pertama yang dikirim olehnya.