EXPSPACE-menyelesaikan masalah

Saat ini saya mencoba untuk menemukan masalah EXPSPACE-lengkap (terutama untuk menemukan inspirasi untuk pengurangan), dan saya terkejut dengan sejumlah kecil hasil yang muncul.

Sejauh ini, saya menemukan ini, dan saya kesulitan memperluas daftar:

• universalitas (atau sifat-sifat lainnya) dari ekspresi reguler dengan eksponensial.
• masalah yang berkaitan dengan sistem penambahan vektor
• game yang tidak dapat diobservasi (lihat misalnya blog ini )
• beberapa fragmen dari FO-LTL, dalam On Computational Complexity of Decidable fragments of First-Order-Linear Temporal Logics

Apakah Anda tahu konteks lain saat kelengkapan EXPSPACE muncul secara alami?

Memperluas contoh yang ditunjukkan oleh Emil Jerabek dalam komentar, masalah lengkap muncul secara alami di seluruh geometri aljabar. Ini dimulai (saya pikir) dengan Masalah Keanggotaan Ideal ( Mayr – Meyer dan Mayr ) dan karenanya perhitungan basis Gröbner. Ini kemudian diperluas ke perhitungan syzygies ( Bayer dan Stillman ). Banyak masalah alami dalam geometri aljabar komputasi akhirnya setara dengan salah satu masalah ini. Juga lihat survei Bayer – Mumford "Apa yang dapat dihitung dalam geometri aljabar?"$\mathsf{EXPSPACE}$

Banyak masalah yang menyelesaikan PSPACE menjadi selesai-EXPSPACE ketika input diberikan "secara ringkas", yaitu, melalui beberapa pengkodean yang memungkinkan Anda menggambarkan input yang biasanya berukuran eksponensial.

Berikut adalah contoh pada automata terbatas (ekuivalen, pada grafik berarah dengan tepi berlabel): memutuskan apakah dua automata menerima bahasa yang sama (memiliki set jalur berlabel yang sama dari titik asal ke titik tujuan) adalah PSPACE-complete. Jika automata (grafik) diberikan oleh rumus Boolean (simpul adalah penilaian v, v ', .. dan ada rumus Boolean yang mengatakan apakah v-> v' adalah edge), masalahnya menjadi EXPSPACE-complete. NB: ada banyak cara lain untuk mendefinisikan secara ringkas grafik / otomat besar, lihat misalnya makalah ini .

Contoh dengan ekspresi reguler cocok dengan pola ini. Memperkenalkan notasi ".. ^ 2" untuk kuadrat memungkinkan Anda menulis ekspresi reguler yang akan sangat besar jika Anda ingin mengembangkan masing-masing "(foo) ^ 2" oleh "foo foo", dan "((bar) ^ 2) ^ 2 "oleh" bar bar bar bar ". Secara alami, beberapa masalah yang menyelesaikan PSPACE tanpa mengkuadratkan menjadi EXPSPACE-lengkap dengan mengkuadratkan yang diizinkan, berikut adalah referensi klasiknya . [NB: Contoh-contoh lain, seperti ekspresi reguler dengan persimpangan atau dengan komplemen tidak jelas cocok dengan pola notasi baru yang berkembang menjadi input eksponensial lebih besar dalam notasi standar.]

Demikian pula, masalah LOGSPACE-complete (misalnya, keterjangkauan dalam grafik berarah) dapat menjadi EXPSPACE-complete jika pengodean ringkas Anda memungkinkan untuk deskripsi grafik dengan ukuran eksponensial ganda.

Intinya: Anda dapat dengan mudah menemukan masalah baru, meskipun mungkin buatan, EXPSPACE-lengkap, dengan mempertimbangkan masalah PSPACE atau LOGSPACE klasik (yang akan Anda temukan banyak) dan memungkinkan untuk pengkodean input ringkas / ringkas / singkat / ..

Perencanaan Temporal dengan tindakan konkuren adalah EXPSPACE-complete, seperti yang ditunjukkan pada

J. Rintanen, “Kompleksitas Perencanaan Temporal Bersamaan,” Prosiding Konferensi Internasional ke-17 tentang Perencanaan dan Penjadwalan Otomatis, hal. 280–287, 2007

Masalahnya kira-kira sebagai berikut (waspadalah dalam makalah di atas itu didefinisikan dengan cara yang berbeda tetapi setara). Mari menjadi terbatas himpunan variabel proposisional dan O himpunan berhingga tindakan , di mana setiap tindakan adalah o = ( d , P s , P e , P o , E s , E e ) , di mana:$A$$O$$o=(d,P_s,P_e,P_o,E_s,E_e)$

• adalah durasi waktu tindakan.$d\in\mathbb{N}$
• $P_s$$P_e$$P_o$$A$
• $E_s$$E_e$$A$

$I$$G$$I$$G$ memegang.

$d$

Sebagian besar kelas standar dari PSPACE (baik, bahkan untuk NP, jika Anda suka) memiliki beberapa masalah ubin sebagai masalah yang lengkap. Masalah ubin seperti itu tidak jauh dari masalah lengkap berbasis mesin Turing alami, tetapi mereka seringkali cukup nyaman sebagai titik awal untuk pengurangan. Singkatnya, masalah ubin memberi Anda satu set ubin yang diizinkan (yaitu: jenis ubin dari mana Anda dapat menggunakan ubin sebanyak yang Anda suka) dan aturan bagaimana mereka dapat dikombinasikan, sering dengan satu set H dari pasangan yang diizinkan secara horizontal dari ubin dan satu set V dari jenis yang diizinkan secara vertikal. Selanjutnya, ubin pertama dan ubin terakhir dapat diberikan dan, tergantung pada versi yang sebenarnya, dan berapa banyak baris dan / atau kolom yang harus dimiliki ubin. Pertanyaan algoritmik adalah, apakah ada ubin yang benar, yaitu, penugasan posisi ke ubin, yang mematuhi semua kendala dan memiliki ubin mulai di posisi kiri bawah dan ubin terakhir di posisi kanan atas. (Ada banyak variasi untuk definisi yang tepat).

Untuk kelas yang ditangani, EXPSPACE, Anda dapat memilih antara (setidaknya) dua versi:

• ubin koridor lebar eksponensial, di mana parameter n diberikan dan pertanyaannya adalah apakah ada ubin dengan 2 ^ n kolom dan sejumlah baris
• permainan ubin exp-times-exp, di mana, mengingat n, ubin harus berukuran 2 ^ n kali 2 ^ n, di mana tujuan pemain pertama adalah mencapai ubin yang benar dan pemain kedua mencoba untuk mencegahnya.

Makalah untuk melihat ini - Bogdan S. Chlebus: "Domino-Tiling Games". J. Comput. Syst. Sci. 32 (3): 374-392 (1986) - Peter van Emde Boas: "Kenyamanan tilings", dalam: Teori Kompleksitas, Logika dan Rekursi, Catatan Kuliah dalam Matematika Murni dan Terapan, Vol. 187, 1997, hlm. 331-363.

contoh & bukti diberikan dalam Pengantar Teori Automata, Bahasa, dan Komputasi Hopcroft / Ullman Thm13.16 bahwa setiap algoritma nondeterministic untuk teori real orde pertama dengan penambahan adalah NExpTime-hard. oleh karena itu mungkin juga NExpSpace-hard kecuali beberapa terobosan teoretis membuktikannya dapat diselesaikan "dalam ruang yang lebih ketat" tetapi tentu saja pertanyaannya serupa (hampir identik?) dengan L =? P. (Dengan kata lain semua masalah NExpTime-hard yang diketahui juga merupakan kandidat dasar untuk NExpSpace-hard, dan jika ada yang terbukti, itu mungkin berarti resolusi terobosan pemisahan kelas kompleksitas terbuka-lama.) buktinya datang dari Fischer, Rabin 1974, "Kompleksitas super-eksponensial aritmatika Presburger," Complexity of Computation(R. Karp ed.). Prosiding Simposium SIAM-AMS dalam Matematika Terapan.