PSPACE bilan yakunlangan muammolar ro'yxati - List of PSPACE-complete problems
Bu erda ko'pincha ma'lum bo'lgan ba'zi muammolar mavjud PSPACE tugallandi sifatida ifodalanganida qaror bilan bog'liq muammolar. Ushbu ro'yxat hech qanday qamrovli emas.
O'yinlar va boshqotirmalar
Umumlashtirildi versiyalari:
- Amazonlar[1]
- Atomix[2]
- Shashka[3]
- Dyson teleskopi o'yini[4]
- Xoch maqsadlari[5]
- Geografiya
- Ko -ozod Boring[6]
- Go-da narvonni suratga olish[7]
- Gomoku[8]
- Olti burchak[9]
- Konane[5]
- Lemmings[10]
- Tugun Kayles[11]
- Poset o'yini[12]
- Reversi[13]
- Daryodan o'tish[14]
- Shoshma soat[14]
- Optimal o'yinni topish Mahjong solitaire[15]
- Sokoban[14]
- Super Mario Bros.[16]
- Qora Pebble o'yini[17]
- Qora oq Pebble o'yini[18]
- Asiklik shag'al o'yini[19]
- Bitta o'yinchi shag'al o'yini[19]
- Token yoniq asiklik yo'naltirilgan grafik o'yinlar:[11]
- Yo'q qilish
- Xit
- Qo'lga olish
- Chegaralarni blokirovka qilish
- Maqsad
- Izlash
Mantiq
- Mantiqiy mantiqiy formulalar
- Birinchi darajali mantiq ning tenglik[20]
- Muvofiqlik intuitivistik propozitsion mantiq
- Mamnuniyat modal mantiq S4[20]
- Birinchi tartib nazariyasi ning natural sonlar voris operatsiyasi ostida[20]
- Birinchi tartib nazariyasi ning natural sonlar standart buyurtma bo'yicha[20]
- Birinchi tartib nazariyasi ning butun sonlar standart buyurtma bo'yicha[20]
- Birinchi tartib nazariyasi ning yaxshi buyurtma qilingan to'plamlar[20]
- Birinchi tartib nazariyasi ning ikkilik qatorlar ostida leksikografik buyurtma[20]
- Birinchi tartib nazariyasi cheklangan Mantiqiy algebra[20]
- Stoxastik to'yinganlik[21]
- Chiziqli vaqtinchalik mantiq qoniqishlilik va modelni tekshirish[22]
Lambda hisobi
Turar joy muammosi oddiygina terilgan lambda hisob-kitobi uchun
Avtomatika va til nazariyasi
O'chirish nazariyasi
Butun sonli elektron baholash[23]
Avtomatika nazariyasi
- So'z muammosi chiziqli cheklangan avtomatlar[24]
- So'z muammosi kvazi real vaqt avtomatika[25]
- Bo'shliq muammosi nondeterministik uchun ikki tomonlama cheklangan holatdagi avtomat[26][27]
- Uchun ekvivalentlik muammosi nondeterministik cheklangan avtomatlar[28][29]
- O'chirmaslik uchun so'z muammosi va bo'shliq muammosi stek avtomatlar[30]
- Cheksiz sonning kesishishining bo'shligi aniqlangan cheklangan avtomatlar[31]
- Ning umumlashtirilgan versiyasi Langton chumoli[32]
- Minimallashtirish nondeterministik cheklangan avtomatlar[33]
Rasmiy tillar
- So'z muammosi kontekstga sezgir til[34]
- Cheklanmagan son uchun kesishgan bo'shliq oddiy tillar [31]
- Muntazam ifoda yulduz ozodligi[35]
- Ekvivalentlik muammosi uchun doimiy iboralar[20]
- Bo'shliq muammosi uchun doimiy iboralar kesishish bilan.[20]
- Ekvivalentlik muammosi yulduzsiz doimiy iboralar kvadratchalar bilan.[20]
- Qoplash uchun chiziqli grammatikalar[36]
- Uchun tarkibiy tenglik chiziqli grammatikalar[37]
- Ekvivalentlik muammosi uchun Muntazam grammatikalar[38]
- Bo'shliq muammosi uchun ET0L grammatika[39]
- So'z muammosi ET0L grammatika[40]
- Daraxt transduser tili tepadan pastga cheklangan holatga keltirilgan daraxt transduserlari uchun a'zolik muammosi[41]
Grafika nazariyasi
- mantiqiy sxemalar sifatida ko'rsatilgan grafikalar bilan ko'plab grafik muammolarning qisqacha versiyalari,[42] buyurdi ikkilik qarorlar diagrammasi[43] yoki boshqa tegishli vakolatxonalar:
- qisqacha grafikalar uchun s-t erishish muammosi. Bu aslida eng oddiy reja mavjudligi muammosi bilan bir xil avtomatlashtirilgan rejalashtirish va rejalashtirish.
- qisqacha grafiklarning tekisligi
- ixcham grafiklarning tezkorligi
- qisqacha grafiklarning bir-biriga bog'liqligi
- qisqacha grafikada evleriya yo'llarining mavjudligi
- Kanadalik sayohatchilar muammosi.[44]
- Marshrutlar tomonidan tanlanganligini aniqlash Chegara shlyuzi protokoli oxir-oqibat berilgan yo'l imtiyozlari to'plami uchun barqaror holatga yaqinlashadi[45]
- Dinamik grafik ishonchliligi.[21]
- Deterministik cheklash mantig'i (cheksiz)[46]
- Nondeterministik cheklash mantig'i (cheksiz)[11]
- Ikkala o'yinchi cheklovlari mantig'i chegaralangan[11]
Boshqalar
- Sonli ufq POMDP (qisman kuzatiladigan Markov qarorlari jarayonlari).[47]
- Yashirin model MDP (hMMDP).[48]
- Markovning dinamik jarayoni.[21]
- Relyatsion ma'lumotlar bazasida qo'shilishning bog'liqligini aniqlash[49]
- Har qanday hisob-kitob Nash muvozanati 2 o'yinchi normal shakldagi o'yin, orqali olish mumkin Lemke-Xovson algoritmi.[50]
- Yo'lakka plitka qo'yish masalasi: to'plami berilgan Vang plitalari, tanlangan plitka va kengligi unary notationda berilgan, balandligi bormi? shunday bir to'rtburchaklar barcha chekka plitalari bo'ladigan tarzda plitka bilan o'ralgan bo'lishi mumkin ?[51][52]
Shuningdek qarang
Izohlar
- ^ R. A. Xirn (2005-02-02). "Amazonlar PSPACE-ni to'ldiradi". arXiv:cs.CC/0502013.
- ^ Markus Xoltser va Stefan Shvun (2004 yil fevral). "ATOMIX-da molekulalarni yig'ish qiyin". Nazariy kompyuter fanlari. 313 (3): 447–462. doi:10.1016 / j.tcs.2002.11.002.
- ^ Ko'p sonli harakatdan so'ng durangni qabul qilish. Aviezri S. Fraenkel (1978). "N x N taxtasidagi shashka murakkabligi - dastlabki hisobot". Kompyuter fanlari bo'yicha XIX yillik simpozium materiallari: 55-64. Iqtibos jurnali talab qiladi
| jurnal =(Yordam bering) - ^ Erik D. Demaine (2009). Dyson teleskopi jumboqining murakkabligi. Imkoniyat bo'lmagan o'yinlar 3.
- ^ a b Robert A. Xirn (2008). "Amazonlar, Konane va o'zaro faoliyat maqsadlari PSPACE bilan to'la". Imkoniyat bo'lmagan o'yinlar 3. Iqtibos jurnali talab qiladi
| jurnal =(Yordam bering) - ^ Lixtenshteyn; Sipser (1980). "Borish polinom-bo'shliqqa qiyin". Hisoblash texnikasi assotsiatsiyasi jurnali. 27 (2): 393–401. doi:10.1145/322186.322201.
- ^ O'tish narvonlari PSPACE bilan to'ldirilgan Arxivlandi 2007-09-30 da Orqaga qaytish mashinasi
- ^ Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku - PSPACE to'liq)". Acta Informatica. 13: 59–66. doi:10.1007 / bf00288536.
- ^ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex PSPACE bilan to'ldirilgan)". Acta Inform. (15): 167–191.
- ^ Viglietta, Jovanni (2015). "Lemmings PSPACE bilan to'la" (PDF). Nazariy kompyuter fanlari. 586: 120–134. doi:10.1016 / j.tcs.2015.01.055.
- ^ a b v d Erik D. Demeyn; Robert A. Xirn (2009). Algoritmlar bilan o'yin o'ynash: algoritmik kombinatoriya o'yinlari nazariyasi. Imkoniyat bo'lmagan o'yinlar 3.
- ^ Grier, Daniel (2012). "O'zboshimchalik bilan yakunlangan Poset o'yinining g'olibini aniqlash PSPACE-Complete". Avtomatika, tillar va dasturlash. Kompyuter fanidan ma'ruza matnlari. 7965. 497-503 betlar. arXiv:1209.1750. doi:10.1007/978-3-642-39206-1_42. ISBN 978-3-642-39205-4.
- ^ Shigeki Ivata va Takumi Kasai (1994). "N * n taxtadagi" Otello "o'yini PSPACE bilan to'ldirilgan". Nazariy kompyuter fanlari. 123 (2): 329–340. doi:10.1016/0304-3975(94)90131-7.
- ^ a b v Eshiting; Demain (2002). "PSPACE-sirg'aladigan blokli boshqotirmalarning to'liqligi va hisoblashning noaniq cheklangan mantiqiy modeli orqali boshqa muammolar". arXiv:cs.CC/0205005.
- ^ A. Kondon, J. Feigenbaum, C. Lund va P. Shor, Tasodifiy munozarachilar va stoxastik funktsiyalarning qattiqligi, Hisoblash bo'yicha SIAM jurnali 26:2 (1997) 369-400.
- ^ Demain; Viglietta; Uilyams (2016). "Super Mario Bros. Bizning fikrimizdan ko'ra qiyinroq / osonroq". Iqtibos jurnali talab qiladi
| jurnal =(Yordam bering) - ^ Gilbert, Lengauer va R. E. Tarjan: Pebbling masalasi polinom fazosida to'la. SIAM hisoblash bo'yicha jurnali, 9-jild, 1980 yil 3-son, 513-524-betlar.
- ^ Filipp Xertel va Toniann Pitassi: Qora-oq pebbling - PSPACE-Complete Arxivlandi 2011-06-08 da Orqaga qaytish mashinasi
- ^ a b Takumi Kasai, Akeo Adachi va Shigeki Ivata: Pebble o'yinlari darslari va to'liq masalalar, SIAM Journal on Computing, 1979 yil 8-jild, 574-586 betlar.
- ^ a b v d e f g h men j k K. Vagner va G. Vechsung. Hisoblash murakkabligi. D. Reydel Nashriyot kompaniyasi, 1986 y. ISBN 90-277-2146-7
- ^ a b v Xristos Papadimitriou (1985). "Tabiatga qarshi o'yinlar". Kompyuter va tizim fanlari jurnali. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5.
- ^ A.P.Sistla va Edmund M. Klark (1985). "Propozitsion chiziqli vaqtinchalik mantiqning murakkabligi". ACM jurnali. 32 (3): 733–749. doi:10.1145/3828.3837.
- ^ Butun sonli davrni baholash
- ^ Garey-Jonson: AL3
- ^ Garey-Jonson: AL4
- ^ Galil, Z. To'liq muammolarning ierarxiyalari. Acta Informatica 6-da (1976), 77-88.
- ^ Garey-Jonson: AL2
- ^ L. J. Stokmeyer va A. R. Meyer. Eksponent vaqtni talab qiladigan so'z muammolari. Hisoblash nazariyasi bo'yicha 5-simpozium materiallari to'plamida, 1973 yil 1-9 betlar.
- ^ Garey-Jonson: AL1
- ^ J. E. Hopkroft va J. D. Ullman. Avtomatika nazariyasi, tillar va hisoblash bilan tanishish, birinchi nashr, 1979 y.
- ^ a b D. Kozen. Tabiiy isbot tizimlari uchun pastki chegaralar. Proc-da. 18-simp. Informatika asoslari to'g'risida, 254–266 betlar, 1977 yil.
- ^ Langtonning chumoli muammosi Arxivlandi 2007-09-27 da Orqaga qaytish mashinasi, "Umumiy nosimmetrik Langtonning chumoli muammosi PSPACE bilan to'la" YAMAGUCHI EIJI va TSUKIJI TATSUIE tomonidan IEIC texnik hisoboti (Elektron, axborot va aloqa muhandislari instituti )
- ^ T. Tszyan va B. Ravikumar. Minimal NFA muammolari qiyin. SIAM Journal on Computing, 22 (6): 1117–1141, 1993 yil dekabr.
- ^ S.-Y. Kuroda, "Tillar sinflari va chiziqli avtomatlar", Axborot va boshqarish, 7(2): 207-223, 1964 yil iyun.
- ^ Muntazam ravishda yulduzcha erkinlik ifodasi PSPACE bilan to'ldirilgan
- ^ Garey-Jonson: AL12
- ^ Garey-Jonson: AL13
- ^ Garey-Jonson: AL14
- ^ Garey-Jonson: AL16
- ^ Garey-Jonson: AL19
- ^ Garey-Jonson: AL21
- ^ Antonio Lozano va Xose L. Balcazar. Qisqacha tasvirlangan grafikalar uchun grafik muammolarning murakkabligi. Manfred Naglda muharrir, Informatika bo'yicha grafik-nazariy tushunchalar, 15-Xalqaro seminar, WG'89, 411-sonli kompyuter fanida ma'ruza yozuvlari, 277-286-betlar. Springer-Verlag, 1990 yil.
- ^ J. Feygenbaum va S. Kannan va M. Y. Vardi va M. Vishvanatan, OBDD sifatida ifodalangan grafikalar bo'yicha muammolarning murakkabligi, Chikago Journal of the Nazariy Computer Science, 5-jild, 1999 y., 5-son.
- ^ C.H. Papadimitriou; M. Yannakakis (1989). "Xaritasiz eng qisqa yo'llar". Kompyuter fanidan ma'ruza matnlari. Proc. 16-ICALP. 372. Springer-Verlag. 610-620 betlar.
- ^ Aleks Fabrikant va Xristos Papadimitriou. O'yin dinamikasining murakkabligi: BGP tebranishlari, cho'kayotgan eklibriyalar va boshqalar Arxivlandi 2008-09-05 da Orqaga qaytish mashinasi. SODA 2008 yilda.
- ^ Erik D. Demeyn va Robert A. Xirn (2008 yil 23-26 iyun). Cheklov mantig'i: Hisoblashni o'yin sifatida modellashtirish uchun yagona asos. Hisoblash murakkabligi bo'yicha 23-yillik IEEE konferentsiyasi materiallari (Murakkablik 2008). Kollej parki, Merilend. 149–162 betlar.
- ^ C.H. Papadimitriou; J.N. Tsitsiklis (1987). "Markov qaror qabul qilish jarayonlarining murakkabligi" (PDF). Amaliyot tadqiqotlari matematikasi. 12 (3): 441–450. doi:10.1287 / moor.12.3.441. hdl:1721.1/2893.
- ^ I. Chades; J. Karvardin; T.G. Martin; S. Nikol; R. Sabbadin; O. Bufet (2012). MOMDPlar: Adaptiv boshqaruv muammolarini modellashtirish uchun echim. AAAI'12.
- ^ Casanova Marko A.; va boshq. (1984). "Inklyuziv bog'liqliklar va ularning funktsional bog'liqliklar bilan o'zaro ta'siri". Kompyuter va tizim fanlari jurnali. 28: 29–59. doi:10.1016/0022-0000(84)90075-8.
- ^ P.W. Goldberg va C.H. Papadimitriou va R. Savani (2011). Homotopiya usulining murakkabligi, muvozanatni tanlash va Lemke-Xovson echimlari. Proc. 52-FOCS. IEEE. 67-76 betlar.
- ^ Maarten Marks (2007). "Modal mantiqning murakkabligi". Patrik Blekbernda; Johan F.A.K. van Bentem; Frank Volter (tahrir). Modal mantiq bo'yicha qo'llanma. Elsevier. p. 170.
- ^ Lyuis, Garri R. (1978). Qarorlar muammosining hal qilinadigan holatlarining predikat hisobi uchun murakkabligi. Kompyuter fanlari asoslari bo'yicha 19 yillik simpozium. IEEE. 35-47 betlar.
Adabiyotlar
- Garey, M.R.; Jonson, D.S. (1979). Kompyuterlar va echib bo'lmaydiganlik: NP to'liqligi nazariyasi uchun qo'llanma. Nyu-York: W.H. Freeman. ISBN 978-0-7167-1045-5.
- Eppshteynning o'yinlarning hisoblash murakkabligi haqidagi sahifasi
- Ierarxik spetsifikatsiyalar uchun PSPACE-to'liq muammolarni taxmin qilishning murakkabligi