Dalam bidang teori kerumitan pengiraan, terutamanya apabila memeriksa kelas kerumitan ruang, hubungan antara PSPACE dan NP adalah menarik minat yang ketara. Untuk menangani soalan secara langsung: ya, terdapat masalah dalam PSPACE yang tidak ada algoritma NP yang diketahui. Penegasan ini berakar umbi dalam definisi dan hubungan antara kelas kerumitan ini.
PSPACE ialah kelas masalah keputusan yang boleh diselesaikan oleh mesin Turing menggunakan jumlah polinomial ruang. Dalam erti kata lain, masalah adalah dalam PSPACE jika terdapat algoritma yang boleh menyelesaikannya menggunakan jumlah memori yang polinomial dalam saiz input. Kelas ini merangkumi pelbagai jenis masalah, beberapa daripadanya agak kompleks dan melibatkan proses pengiraan yang rumit.
NP, sebaliknya, ialah kelas masalah keputusan yang penyelesaian yang dicadangkan boleh disahkan dalam masa polinomial oleh mesin Turing yang menentukan. Ini bermakna jika seseorang memberikan anda penyelesaian calon kepada masalah dalam NP, anda boleh menyemak ketepatan penyelesaian itu dengan cepat, khususnya dalam masa polinomial berbanding saiz input.
Hubungan antara kedua-dua kelas ini adalah sedemikian rupa sehingga NP ialah subset PSPACE. Ini kerana sebarang masalah yang boleh disahkan dalam masa polinomial juga boleh diselesaikan dalam ruang polinomial. Untuk memahami sebabnya, pertimbangkan bahawa pengesah masa polinomial hanya boleh membaca nombor polinomial bit input dan penyelesaian yang dicadangkan. Oleh itu, ia boleh disimulasikan oleh mesin ruang polinomial yang menjejaki kedudukan yang telah dibaca dan operasi yang telah dilakukannya.
Bagaimanapun, sebaliknya tidak diketahui kebenarannya; iaitu, tidak diketahui sama ada PSPACE ialah subset NP. Malah, dipercayai secara meluas bahawa PSPACE mengandungi masalah yang tiada dalam NP, walaupun ini belum terbukti secara rasmi. Kepercayaan ini berdasarkan kepada kewujudan masalah dalam PSPACE yang nampaknya memerlukan lebih daripada masa polinomial untuk diselesaikan, walaupun ia boleh diselesaikan dengan ruang polinomial.
Salah satu contoh kanonik masalah dalam PSPACE yang tidak diketahui terdapat dalam NP ialah masalah Quantified Boolean Formula (QBF). QBF ialah generalisasi masalah kepuasan Boolean (SAT), iaitu NP-lengkap. Walaupun SAT bertanya sama ada wujud penetapan nilai kebenaran kepada pembolehubah yang menjadikan formula Boolean yang diberikan benar, QBF melibatkan pengkuantiti bersarang ke atas pembolehubah, seperti "untuk semua x, wujud adalah sedemikian rupa sehingga formula itu benar." Kehadiran pengkuantiti ini menjadikan QBF jauh lebih kompleks. QBF adalah PSPACE-lengkap, bermakna ia sekeras mana-mana masalah dalam PSPACE. Sekiranya terdapat algoritma NP untuk QBF, ia akan membayangkan bahawa NP bersamaan dengan PSPACE, hasil yang akan menjadi terobosan dan secara meluas dianggap tidak mungkin.
Contoh ilustrasi lain ialah masalah menentukan pemenang dalam permainan umum, seperti versi umum catur atau Go, dimainkan pada papan N x N. Masalah ini melibatkan bilangan pergerakan dan konfigurasi yang berpotensi eksponen, tetapi ia boleh diputuskan menggunakan ruang polinomial dengan meneroka semua keadaan permainan yang mungkin secara sistematik. Masalah-masalah ini juga PSPACE-lengkap, seterusnya mencadangkan wujudnya masalah dalam PSPACE yang tiada dalam NP.
Untuk menyelidiki lebih mendalam mengapa masalah tertentu dalam PSPACE dipercayai berada di luar NP, pertimbangkan sifat pengiraan sempadan ruang berbanding sempadan masa. Ruang polinomial membenarkan bilangan langkah pengiraan yang berpotensi eksponen, selagi ruang yang digunakan kekal dalam sempadan polinomial. Ini sangat berbeza dengan NP, di mana masa adalah polinomial bersempadan. Masa eksponen yang dibenarkan oleh ruang polinomial boleh digunakan untuk menyelesaikan masalah yang melibatkan carian menyeluruh ke atas ruang eksponen yang besar, seperti yang ditemui dalam QBF dan permainan umum.
Selain itu, terdapat pembinaan teori yang rumit yang menyokong lagi perbezaan antara PSPACE dan NP. Sebagai contoh, konsep selang-seli, yang diperkenalkan oleh Chandra, Kozen, dan Stockmeyer, menyamaratakan nondeterminisme dan membawa kepada kelas AP (masa polinomial berselang-seli). Telah ditunjukkan bahawa AP menyamai PSPACE, dengan itu memberikan perspektif yang berbeza tentang kuasa pengiraan ruang polinomial. Pergantian melibatkan urutan pengkuantiti kewujudan dan universal, mencerminkan struktur QBF, dan mempamerkan kerumitan yang wujud dalam masalah PSPACE.
Perlu juga diperhatikan bahawa pemisahan kelas kerumitan adalah persoalan terbuka asas dalam sains komputer teori. Masalah P vs NP yang terkenal ialah kes khas bagi siasatan yang lebih luas ini. Begitu juga, persoalan sama ada NP bersamaan dengan PSPACE masih tidak dapat diselesaikan. Walau bagaimanapun, konsensus di lapangan, berdasarkan kajian meluas dan sifat masalah yang diketahui, adalah PSPACE berkemungkinan mengandungi masalah yang tidak ada dalam NP.
Kewujudan masalah dalam PSPACE yang tiada algoritma NP yang diketahui disokong oleh definisi dan perhubungan antara kelas kerumitan ini, serta oleh contoh konkrit seperti QBF dan masalah permainan umum. Contoh-contoh ini menyerlahkan proses pengiraan yang rumit dan berpotensi eksponen yang boleh diuruskan dalam ruang polinomial tetapi tidak mungkin terhad kepada masa polinomial, sekali gus meletakkannya di luar bidang NP.
Soalan dan jawapan terbaru lain mengenai kerumitan:
- Adakah kelas PSPACE tidak sama dengan kelas EXPSPACE?
- Adakah kelas kerumitan P subset kelas PSPACE?
- Bolehkah kita membuktikan bahawa kelas Np dan P adalah sama dengan mencari penyelesaian polinomial yang cekap untuk sebarang masalah lengkap NP pada TM yang menentukan?
- Bolehkah kelas NP sama dengan kelas EXPTIME?
- Bolehkah masalah SAT menjadi masalah lengkap NP?
- Bolehkah masalah berada dalam kelas kerumitan NP jika terdapat mesin turing bukan deterministik yang akan menyelesaikannya dalam masa polinomial
- NP ialah kelas bahasa yang mempunyai pengesah masa polinomial
- Adakah P dan NP sebenarnya adalah kelas kerumitan yang sama?
- Adakah setiap bahasa bebas konteks dalam kelas kerumitan P?
- Adakah terdapat percanggahan antara takrifan NP sebagai kelas masalah keputusan dengan pengesah masa polinomial dan fakta bahawa masalah dalam kelas P juga mempunyai pengesah masa polinomial?
Lihat lebih banyak soalan dan jawapan dalam Kerumitan