Masalah lengkap NEXP

Ada banyak masalah NP-selesai di sekitar dan sumber mengumpulkan mereka, misalnya lihat buku oleh Garey dan Johnson. Saya akan tertarik untuk melihat daftar masalah lengkap NEXP juga. Apakah ada satu tersedia? Karena saya anggap tidak ada, saya membuka pertanyaan ini (apakah ini seharusnya merupakan komunitas wiki? Saya tidak tahu tentang hal ini).

Idealnya daftar harus mencakup "jenis" yang berbeda dari masalah lengkap NEXP, mungkin dengan beberapa redundansi yang sehat untuk mendapatkan gambaran besar, tetapi tanpa mengulangi terlalu banyak. Sebagai contoh, baik untuk memiliki dua atau tiga versi ringkas yang berbeda dari masalah NP-lengkap yang sama sebagai contoh, jika pengkodean ringkas datang dalam bentuk yang sedikit berbeda. Tidak selusin. Cara bersih untuk menambahkan redundansi adalah dengan menambahkan klausa formulir "Juga NEXP-lengkap jika BLAH". Klausa formulir "Tetap NEXP-lengkap jika grafik input memiliki tingkat paling banyak BLAH" juga diterima.

Akhirnya, izinkan saya menambahkan preferensi pribadi. Saya terutama tertarik pada masalah lengkap rasa "aljabar", jika ada. Misalnya, masalah # P-complete favorit saya adalah permanen karena rasanya aljabar. Saya harap kesetaraan NEXP = MIP juga dapat memberikan beberapa masalah lengkap NEXP aljabar yang tidak saya sadari.

Untuk beberapa masalah NP-lengkap, ada varian SUCCINCT yang lengkap-NEXP.

Contohnya adalah SUCCINCT HAMILTON PATH:

• Sirkuit Boolean dengan input 2 n dan satu output mewakili grafik pada simpul 2 ⁿ . Untuk menentukan apakah ada tepi antara simpul i dan j , masing-masing enkode i dan j dalam n bit, dan masukkan rangkaiannya ke sirkuit: ada tepi di antara simpul-simpul ini jika output sirkuit benar. Dengan sirkuit seperti itu, apakah ada jalur Hamilton dalam grafik yang diwakili oleh sirkuit?

Demikian pula, ada SUCCINCT 3SAT, SUCCINCT KNAPSACK, dll.

Referensi

• Hana Galperin, dan Avi Wigderson (1983), "Representasi ringkas grafik", Informasi dan Kontrol 56: 3, hlm. 183–198.

Lihat http://arxiv.org/abs/0905.2419 oleh Gottesman dan Irani. Ini adalah contoh yang rapi. Pada dasarnya, kita semua terbiasa dengan gagasan bahwa kepuasan kendala dapat menjadi masalah NP-lengkap (tergantung pada geometri, dll ...) Namun, mereka mempertimbangkan situasi di mana semua kendala diberikan sebelumnya dan satu-satunya hal yang diizinkan bervariasi adalah seberapa besar sistemnya. Namun, ini ternyata masih sulit jika Anda menyandikan masalah dalam ukuran sistem. Artinya, masalah ditentukan dengan memberikan string N bit, memberikan ukuran sistem dari 0 hingga 2 ^ N-1. Jadi, ukuran sistem secara eksponensial lebih besar dari ukuran input. Mereka menunjukkan bahwa ini adalah NEXP-complete (dan bahwa analog kuantum adalah QMA_EXP-complete).

Mari saya mulai dengan yang kanonik:

Diberikan mesin Turing non-deterministik dan bilangan bulat n yang ditulis dalam biner, apakah ada jalur komputasi M yang menerima string kosong paling banyak dalam n langkah?$M$$n$$M$$n$

Juga selesai NEXP jika ditulis dalam unary dan kami meminta paling banyak 2 n langkah.$n$$2^n$

$\cup$$\cdot$${}^2$

Ekspresi reguler juga

• $0$
• $1$
• $e\cup f$
• $e\cdot f$
• $e^2$

Ekspresi ini mewakili set

• $L(0)=\{0\}$
• $L(1)=\{1\}$
• $L(e\cup f)=L(e)\cup L(f)$
• $L(e\cdot f)=\{ab\mid a\in L(e), b\in L(f)\}$
• $L(e^2)=L(e\cdot e)$

masing-masing.

Perhatikan bahwa jika kita mengizinkan bintang Kleene (nol atau lebih salinan ekspresi) sebagai operator keempat (selain penyatuan, penggabungan, dan kuadrat), maka masalah mengenali apakah dua ekspresi reguler mewakili bahasa yang berbeda menjadi lengkap EXPSPACE .

LJ Stockmeyer, AR Meyer, " Masalah kata membutuhkan waktu eksponensial ", 5 STOC, 1973.

SCHÖNFINKEL – BERNAYS SAT

• $∃x_1 ∃x_2 \ldots ∀y_1 ∀y_2 \ldots φ$$φ$

Referensi

• HR Lewis (1980), " Hasil Kompleksitas untuk kelas formula kuantitatif ", Jurnal Ilmu Komputer dan Sistem 21, hlm. 317-353.