Masalah yang dapat diputuskan tetapi tidak dapat diverifikasi dalam waktu polinomial

Saat bekerja pada proyek yang agak tidak terkait untuk Suresh I baru-baru ini menemukan beberapa pekerjaan yang dilakukan oleh Page dan Opper tentang sistem yang dapat dikomposisikan oleh Pengguna dan sebagian dari pekerjaan mereka secara singkat membahas masalah yang tidak dapat diverifikasi dalam waktu polinomial. Saya tidak dapat menemukan banyak informasi tentang masalah lain yang tidak dapat diverifikasi dalam waktu polinomial atau analisis masalah seperti itu. Saya bertanya-tanya apakah ada di antara Anda yang tahu masalah seperti itu dan / atau bagaimana menganalisisnya.

Seperti yang dinyatakan dalam komentar, cara yang lebih baik untuk mengungkapkan pertanyaan ini adalah: Masalah apa yang dapat diputuskan tetapi di luar NP?

Hal yang paling penting untuk diwujudkan dari sudut pandang teoritis adalah bahwa NP sebenarnya adalah kelas yang relatif kecil dari semua bahasa yang dapat dipilih. Yang mengatakan, banyak masalah menarik dalam ilmu komputer terletak di dalam NP sehingga mereka mendapatkan banyak perhatian.

$NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$

Kelas PH, PSPACE, dan EXP berisi banyak masalah "menarik" di , yang saya anggap Anda tanyakan dalam pertanyaan ini. Sejauh ini NEXP telah mendapatkan semua perhatian karena adalah satu-satunya penahanan yang tepat yang dapat kita buktikan (oleh teorema hierarki waktu nondeterministik, seperti yang saya sebutkan di atas).$R \setminus NP$$NP \subsetneq NEXP$

Berikut adalah beberapa contoh konkret masalah yang menarik di beberapa kelas lain ini:

• Menentukan apakah seorang pemain memiliki strategi kemenangan dalam catur atau Go (disesuaikan dengan papan nxn) adalah lengkap-EXP.
• MAJ-SAT, masalah menentukan apakah lebih dari setengah tugas untuk variabel dalam formula boolean memenuhi formula itu, ada di PSPACE. Ini juga lengkap untuk PP kelas kecil.
• EXACT-CLIQUE, masalah menentukan apakah klik terbesar dalam grafik adalah ukuran persis k, ada di , bagian dari level kedua hirarki polinomial.$\Sigma_2^P$

Meluas pada komentar Hsien-Chih Chang, setiap masalah sulit NEXP tidak bisa dalam NP, sehingga menurut definisi tidak dapat diverifikasi dalam waktu polinomial.

Seseorang dapat menggunakan teorema hierarki waktu nondeterministik untuk melihat bahwa NP secara ketat terkandung dalam NEXP. Oleh karena itu, kita dapat yakin bahwa dengan masalah NEXP-hard, itu tidak dalam NP atau kita akan dipimpin dalam kontradiksi.