Masalah “alami” yang dapat diketahui tidak ada dalam NP.

Setiap kali saya mengajar NP-Completeness, siswa bertanya "apakah ada masalah yang diketahui bukan milik NP?"

Bagaimana Anda menjawabnya? Saya biasanya memberi mereka masalah yang tidak dapat diputuskan sebagai contoh, tetapi ini sering tidak berjalan dengan baik: (a) jika saya memberi mereka Masalah Pemutusan, mereka pikir itu adalah kasus sudut bisu, dan (b) jika saya memberi mereka Diophantine Equations mereka tidak melihat mengapa itu tidak di NP (Anda dapat memeriksa solusi dalam waktu-poli ... tancapkan saja mereka! Saya mengalami kesulitan melucuti mereka dari pendekatan ini.)

Saya ingin memberi mereka sesuatu seperti QBF sebagai contoh, tetapi tidak ada pemisahan yang terbukti.

Saran?

Salah satu kemungkinan adalah masalah yang selesai-EXPSPACE. NP sepele di PSPACE, yang secara ketat terkandung dalam EXPSPACE. Satu masalah yang EXPSPACE-lengkap memutuskan apakah ekspresi reguler yang memungkinkan eksponensial adalah semua $\Sigma^*$ .

Karena Anda menekankan masalah alami, Berikut ini adalah sangat alami - masalah lengkap yang tidak ada dalam N P : Masalah Ubin Persegi: Diberikan sekumpulan ubin hingga, Apakah ubin itu berukuran persegi Ukuran 2 n x$NEXP$$NP$$2^n$ ?$2^n$

Perhatikan bahwa ketika ukuran persegi adalah x n ( n dikodekan dalam unary) maka masalahnya menjadi$n$$n$$n$ -complete.$NP$

Untuk kelengkapan ubin persegi, periksa referensi.$NEXP$

[1] Christos H. Papadimitriou. Kompleksitas Komputasi. Addison-Wesley, Reading, Massachusetts, 1994

Masalah apa pun yang diselesaikan untuk atau 2 E X P T I M E diketahui tidak berada dalam N P (menurut teorema hierarki waktu). Demikian pula untuk N E X P S P A C E dan E X P S P A C $NEXPTIME$$EXPTIME$$NP$$NEXPSPACE$$EXPSPACE$(berdasarkan hierarki ruang + simulasi). Anda bisa sering mendapatkan masalah "palsu" dengan melapisi, tetapi masalah alami yang lengkap untuk kelas-kelas ini tampaknya tidak terlalu umum (mungkin karena mereka sangat sulit!), Tetapi di sini ada beberapa:

EXPSPACE: Kesetaraan
ekspresi reguler dengan operator eksponensial

2-EXPTIME: Satisfiability
for CTL * (a temporal logic)
Satisfiability for ATL *
Masalah keputusan untuk aritmatika Presburger

Contoh sederhana adalah fungsi tetrasi , yang bahkan tidak dalam ELEMENTARY . Anda dapat menggunakan beberapa versi keputusan itu.

$g(n)$$f(n+1) = o(g(n))$

$\operatorname{NTIME}(f(n)) \subsetneq \operatorname{NTIME}(g(n))$ .

Jadi, misalnya, masalah NEXP-complete tidak ada dalam NP. Mengutip dari Wikipedia :

Satu set penting masalah lengkap NEXPTIME berhubungan dengan sirkuit ringkas. Sirkuit ringkas adalah mesin sederhana yang digunakan untuk menggambarkan grafik dalam ruang yang kurang eksponensial. Mereka menerima dua angka titik sebagai input dan output apakah ada keunggulan di antara mereka. Jika memecahkan masalah pada grafik dalam representasi alami, seperti matriks adjacency, adalah NP-lengkap, maka menyelesaikan masalah yang sama pada representasi rangkaian ringkas adalah NEXPTIME-complete, karena input secara eksponensial lebih kecil. Sebagai satu contoh sederhana, menemukan jalur Hamiltonian untuk grafik yang dikodekan adalah lengkap-NEXPTIME.

Lihat juga bagian "Masalah Singkat" di halaman 492 dari buku Papadimitriou .

Sistem saluran adalah seperangkat automata terbatas dengan saluran komunikasi tempat mereka dapat mengirim pesan. Pesan adalah surat dari alfabet. Dalam sistem saluran yang hilang, pesan dapat dijatuhkan: surat yang dikirim melalui saluran dapat hilang. Masalah jangkauan untuk sistem saluran lossy adalah decidable tetapi non-primitif rekursif.

Sebagai contoh yang lebih lembut, masalah jangkauan untuk sistem penambahan vektor adalah EXPSpace keras.