รายชื่อปัญหา PSPACE ที่สมบูรณ์

Q: แคลคูลัสแลมบ์ดา

ปัญหาการจำกัดประเภท สำหรับแคลคูลัสแลมบ์ดาแบบกำหนดประเภทอย่างง่าย

ต่อไปนี้คือตัวอย่างปัญหาที่เป็นที่รู้จักกันทั่วไปบางส่วนที่สามารถแก้ได้ด้วยวิธีPSPACE-completeเมื่อแสดงในรูปแบบของปัญหาการตัดสินใจรายชื่อนี้ไม่ได้ครอบคลุมทุกปัญหาแต่อย่างใด

เกมและปริศนา

รูปแบบ ทั่วไปของ:

อเมซอน^{[ 1 ]}
อะโตมิกซ์^{[ 2 ]}
หมากรุกหากการเสมอกันถูกบังคับหลังจากจำนวนพหุนามของการเดินที่ไม่กระโดด^{[ 3 ]}
เกมกล้องโทรทรรศน์ไดสัน^{[ 4 ]}
วัตถุประสงค์ที่ขัดแย้งกัน^{[ 5 ]}
ภูมิศาสตร์
เกม Instant Insanityเวอร์ชันสำหรับผู้เล่นสองคน
โค -ฟรีโก^{[ 6 ]}
การจับบันไดในเกมโกะ^{[ 7 ]}
โกโมกุ^{[ 8 ]}
เลขฐานสิบหก^{[ 9 ]}
โคนาเนะ^{[ 5 ]}
เลมมิงส์^{[ 10 ]}
โหนด Kayles ^{[ 11 ]}
เกมโพเซ็ต^{[ 12 ]}
ย้อนกลับ^{[ 13 ]}
การข้ามแม่น้ำ^{[ 14 ]}
ชั่วโมงเร่งด่วน^{[ 14 ]}
การค้นหาการเล่นที่เหมาะสมที่สุดในไพ่นกกระจอกโซลิแทร์^{[ 15 ]}
สแคร็บเบิล^{[ 16 ]}
โซโคบัน^{[ 14 ]}
ซูเปอร์มาริโอ บราเธอร์ส^{[ 17 ]}
เกมแบล็ก เพ็บเบิล ^{[ 18 ]}
เกมหินขาวดำ^{[ 19 ]}
เกมหินกรวด แบบไม่มีวงจร^{[ 20 ]}
เกมหินกรวดสำหรับผู้เล่นคนเดียว^{[ 20 ]}
โทเค็นบน เกม กราฟทิศทางแบบไม่มีวงจร : ^{[ 11 ]}

ตรรกะ

สูตรบูลีนเชิงปริมาณ
ตรรกะลำดับแรกของความเท่าเทียมกัน^{[ 21 ]}
ความสามารถในการพิสูจน์ในตรรกศาสตร์เชิงประพจน์แบบสัญชาตญาณนิยม
ความพึงพอใจในตรรกะโมดอล S4 ^{[ 21 ]}
ทฤษฎีลำดับแรกของจำนวนธรรมชาติภายใต้การดำเนินการสืบทอด^{[ 21 ]}
ทฤษฎีลำดับแรกของจำนวนธรรมชาติภายใต้ลำดับมาตรฐาน^{[ 21 ]}
ทฤษฎีลำดับแรกของจำนวนเต็มภายใต้ลำดับมาตรฐาน^{[ 21 ]}
ทฤษฎีลำดับแรกของเซตที่มีลำดับที่ดี^{[ 21 ]}
ทฤษฎีลำดับแรกของสตริงไบนารีภายใต้การเรียงลำดับแบบพจนานุกรม^{[ 21 ]}
ทฤษฎีลำดับแรกของพีชคณิตบูลีน จำกัด ^{[ 21 ]}
ความพึงพอใจแบบสุ่ม^{[ 22 ]}
ตรรกะเชิงเวลาเชิงเส้นความพึงพอใจ และการตรวจสอบแบบจำลอง^{[ 23 ]}

แคลคูลัสแลมบ์ดา

ปัญหาการจำกัดประเภทสำหรับแคลคูลัสแลมบ์ดาแบบกำหนดประเภทอย่างง่าย

ออโตมาตาและทฤษฎีภาษา

ทฤษฎีกราฟ

เวอร์ชันย่อของปัญหากราฟจำนวนมาก โดยกราฟแสดงเป็นวงจรบูลีน^{[ 43 ]}แผนภาพการตัดสินใจไบนารีแบบเรียงลำดับ [ ^{44 ] หรือ}การแสดงอื่นๆ ที่เกี่ยวข้อง:
- ปัญหาการเข้าถึงได้ง่ายที่สุดสำหรับกราฟแบบกระชับ โดยพื้นฐานแล้วปัญหานี้เหมือนกับปัญหาการมีอยู่ของแผนงานที่ง่ายที่สุดในการวางแผนและจัดตารางเวลาอัตโนมัติ
- ความเรียบของกราฟกระชับ
- ความไม่มีวัฏจักรของกราฟกระชับ
- ความเชื่อมโยงของกราฟแบบกระชับ
- การมีอยู่ของเส้นทางออยเลอร์ในกราฟแบบกระชับ
ตรรกะข้อจำกัดสองผู้เล่นแบบจำกัด^{[ 11 ]}
ปัญหาของนักเดินทางชาวแคนาดา^{[ 45 ]}
การพิจารณาว่าเส้นทางที่เลือกโดยโปรโตคอลเกตเวย์ชายแดนจะบรรจบกันในสถานะที่เสถียรสำหรับชุดการตั้งค่าเส้นทางที่กำหนดหรือไม่^{[ 46 ]}
ตรรกะข้อจำกัดเชิงกำหนด(ไม่จำกัด) ^{[ 47 ]}
ความน่าเชื่อถือของกราฟแบบไดนามิก^{[ 22 ]}
เกมระบายสีกราฟ^{[ 48 ]}
เกม Node Kayles และเกมการสร้างคลิก : ^{[ 49 ]}ผู้เล่นสองคนผลัดกันเลือกจุดยอด และกราฟย่อยที่เหนี่ยวนำจะต้องเป็นเซตอิสระ (หรือคลิก) ผู้เล่นคนสุดท้ายที่เล่นจะเป็นผู้ชนะ
ตรรกะข้อจำกัดแบบไม่กำหนด (ไม่จำกัด) ^{[ 11 ]}

คนอื่น

POMDPs ขอบเขตจำกัด (กระบวนการตัดสินใจแบบมาร์คอฟที่สังเกตได้บางส่วน) ^{[ 50 ]}
โมเดล MDP ที่ซ่อนอยู่ (hmMDPs) ^{[ 51 ]}
กระบวนการมาร์คอฟแบบไดนามิก^{[ 22 ]}
การตรวจจับการพึ่งพาการรวมในฐานข้อมูลเชิงสัมพันธ์^{[ 52 ]}
การคำนวณสมดุลแนช ใดๆ ของ เกมรูปแบบปกติ 2 ผู้เล่นซึ่งอาจได้รับผ่านอัลกอริทึม Lemke– Howson ^{[ 53 ]}
ปัญหาการปูกระเบื้องทางเดิน: เมื่อกำหนดชุดกระเบื้อง Wangกระเบื้องที่เลือกและความกว้างที่กำหนดในสัญกรณ์เอกภาค จะมีความสูงใดบ้างที่สามารถปูกระเบื้องสี่เหลี่ยมผืนผ้าได้โดยที่กระเบื้องขอบทั้งหมดเป็น? ^[⁵⁴^]^[⁵⁵^] $T_{0}$ $n$ $m$ $n\times m$ $T_{0}$

ดูเพิ่มเติม

รายชื่อปัญหา NP-complete

หมายเหตุ

^ RA Hearn (2 กุมภาพันธ์ 2548). "Amazons คือ PSPACE-complete". arXiv : cs.CC/0502013 .
^ Markus Holzer และ Stefan Schwoon (กุมภาพันธ์ 2547) "การประกอบโมเลกุลใน ATOMIX นั้นยาก"วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี 313 ( 3): 447– 462. doi : 10.1016/j.tcs.2002.11.002 .
^ Aviezri S. Fraenkel (1978). "ความซับซ้อนของหมากรุกบนกระดาน N x N - รายงานเบื้องต้น". การประชุมวิชาการประจำปีครั้งที่ 19 ด้านวิทยาการคอมพิวเตอร์ : 55– 64.
^ Erik D. Demaine (2009). ความซับซ้อนของปริศนากล้องโทรทรรศน์ไดสันเล่มที่ เกมแห่งโอกาส 3.
^ ^a ^b Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3 .
^ Lichtenstein; Sipser (1980). "Go is polynomial-space hard" . Journal of the Association for Computing Machinery . 27 (2): 393– 401. doi : 10.1145/322186.322201 . S2CID 29498352 .
^บันได Go เสร็จสมบูรณ์แล้วใน PSPACE เก็บถาวรเมื่อ 30 กันยายน 2007 ที่ Wayback Machine
↑สเตฟาน ไรช์ (1980) "Gobang ist PSPACE-vollstandig (Gomoku คือ PSPACE ที่สมบูรณ์)" แอกต้า อินฟอร์เมติกา . 13 : 59– 66. ดอย : 10.1007/bf00288536 . S2CID 21455572 .
↑สเตฟาน ไรช์ (1981) "Hex ist PSPACE-vollständig (Hex คือ PSPACE-complete)" แอกต้า อินฟอร์เมติกา (15): 167– 191.
^ Viglietta, Giovanni (2015). "Lemmings Is PSPACE-Complete" (PDF) . Theoretical Computer Science . 586 : 120– 134. arXiv : 1202.6581 . doi : 10.1016/j.tcs.2015.01.055 .
^ ^a ^b ^c ^d Erik D. Demaine; Robert A. Hearn (2009). การเล่นเกมด้วยอัลกอริทึม: ทฤษฎีเกมเชิงผสมแบบอัลกอริทึมเล่มที่ เกมแห่งโอกาส 3.
^ Grier, Daniel (2013). "การตัดสินผู้ชนะของเกมโพเซตจำกัดใดๆ นั้นเป็น PSPACE-Complete" Automata, Languages, and Programming . Lecture Notes in Computer Science. Vol. 7965. pp. 497– 503. arXiv : 1209.1750 . doi : 10.1007/978-3-642-39206-1_42 . ISBN 978-3-642-39205-4. S2CID 13129445 .
^ Shigeki Iwata และ Takumi Kasai (1994). "เกม Othello บนกระดาน n*n สมบูรณ์แบบ PSPACE" . วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี . 123 (2): 329– 340. doi : 10.1016/0304-3975(94)90131-7 .
^ ^a ^b ^c Hearn ; Demaine (2002). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv : cs.CC/0205005 .
^ A. Condon , J. Feigenbaum, C. Lund และ P. Shor , ผู้โต้วาทีแบบสุ่มและความยากของการประมาณฟังก์ชันสุ่ม, SIAM Journal on Computing 26:2 (1997) 369-400
^ Lampis, Michael; Mitsou, Valia; Sołtys, Karolina (2015). "Scrabble สมบูรณ์แบบ PSPACE" . วารสารการประมวลผลข้อมูล . 23 (3): 284– 292. arXiv : 1201.5298 . doi : 10.2197/ipsjjip.23.284 .
^ Demaine, Erik D.; Viglietta, Giovanni; Williams, Aaron (มิถุนายน 2016). "Super Mario Bros. ยากกว่า/ง่ายกว่าที่เราคิด" (PDF) . การประชุมนานาชาติว่าด้วยความสนุกกับอัลกอริทึม ครั้งที่ 8 .บทสรุปโดยย่อ: Sabry, Neamat (28 เมษายน 2020). "Super Mario Bros ยาก/ง่ายกว่าที่เราคิด" . Medium .
^ Gilbert, Lengauer และ RE Tarjan: ปัญหาการโยนก้อนหินนั้นสมบูรณ์ในปริภูมิพหุนาม SIAM Journal on Computing เล่มที่ 9 ฉบับที่ 3 ปี 1980 หน้า 513-524
^ Philipp Hertel และ Toniann Pitassi : Black-White Pebbling คือ PSPACE-Complete ที่เก็บถาวรเมื่อ 2011-06-08 ที่ Wayback Machine
^ ^a ^b Takumi Kasai, Akeo Adachi และ Shigeki Iwata: ประเภทของ Pebble Games และ Complete Problems , SIAM Journal on Computing, เล่มที่ 8, 1979, หน้า 574-586
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k K. Wagner และ G. Wechsung. ความซับซ้อนของการคำนวณ . สำนักพิมพ์D. Reidel , 1986. ISBN 90-277-2146-7
^ ^a ^b ^c Christos Papadimitriou (1985). "เกมต่อต้านธรรมชาติ" . วารสารวิทยาการคอมพิวเตอร์และระบบ . 31 (2): 288– 301. doi : 10.1016/0022-0000(85)90045-5 .
^ APSistla และEdmund M. Clarke (1985). "ความซับซ้อนของตรรกะเชิงเวลาเชิงเส้นแบบประพจน์"วารสารของ ACM 32 ( 3): 733– 749. doi : 10.1145/3828.3837 . S2CID 47217193 .
^การประเมินวงจรจำนวนเต็ม
↑แกรีย์แอนด์จอห์นสัน (1979) , AL3.
↑แกรีย์แอนด์จอห์นสัน (1979) , AL4.
↑แกรีย์แอนด์จอห์นสัน (1979) , AL2.
^ Galil, Z.ลำดับชั้นของปัญหาที่สมบูรณ์ใน Acta Informatica 6 (1976), 77-88.
↑แกรีย์แอนด์จอห์นสัน (1979) , AL1.
^ LJ Stockmeyerและ AR Meyer. โจทย์ปัญหาที่ต้องใช้เวลาแบบเลขชี้กำลัง ในรายงานการประชุมสัมมนาทฤษฎีการคำนวณครั้งที่ 5 หน้า 1–9, 1973
^ JE Hopcroft และ JD Ullman.บทนำสู่ทฤษฎีออโตมาตา ภาษา และการคำนวณ ฉบับพิมพ์ครั้งแรก ปี 1979
^ ^a ^b D. Kozen. ขอบเขตล่างสำหรับระบบพิสูจน์ตามธรรมชาติ ใน Proc. 18th Symp. on the Foundations of Computer Science, หน้า 254–266, 1977.
^ปัญหาของมดของแลงตันเก็บถาวรเมื่อ 27 กันยายน 2007 ที่ Wayback Machineหัวข้อ "ปัญหาของมดของแลงตันแบบสมมาตรทั่วไปนั้นสมบูรณ์แบบ PSPACE" โดย YAMAGUCHI EIJI และ TSUKIJI TATSUIE ในรายงานทางเทคนิคของ IEIC (สถาบันวิศวกรอิเล็กทรอนิกส์ สารสนเทศ และการสื่อสาร )
^ T. Jiang และ B. Ravikumar. ปัญหา NFA ขั้นต่ำนั้นยาก SIAM Journal on Computing, 22(6):1117–1141, ธันวาคม 1993
^ S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control , 7 (2): 207–223, มิถุนายน 1964
↑แบร์นาตสกี, ลาสซโล. "การไม่มีดาวของนิพจน์ปกติคือ PSPACE-Complete" (PDF ) สืบค้นเมื่อ2021-01-13 .
↑แกรีย์แอนด์จอห์นสัน (1979) , AL12.
↑แกรีย์แอนด์จอห์นสัน (1979) , AL13.
↑แกรีย์แอนด์จอห์นสัน (1979) , AL14.
↑แกรีย์แอนด์จอห์นสัน (1979) , AL16.
↑แกรีย์แอนด์จอห์นสัน (1979) , AL19.
↑แกรีย์แอนด์จอห์นสัน (1979) , AL21.
^ Antonio Lozano และ Jose L. Balcazar. ความซับซ้อนของปัญหาเกี่ยวกับกราฟสำหรับกราฟที่แสดงอย่างกระชับ ใน Manfred Nagl บรรณาธิการ, แนวคิดเชิงทฤษฎีกราฟในวิทยาศาสตร์คอมพิวเตอร์, การประชุมเชิงปฏิบัติการนานาชาติครั้งที่ 15, WG'89, หมายเลข 411 ใน Lecture Notes in Computer Science, หน้า 277–286. Springer-Verlag, 1990.
^ J. Feigenbaum และ S. Kannan และ MY Vardi และ M. Viswanathan, ความซับซ้อนของปัญหาบนกราฟที่แสดงเป็น OBDD, Chicago Journal of Theoretical Computer Science, เล่ม 5, ฉบับที่ 5, 1999
^ CH Papadimitriou; M. Yannakakis (1989). "เส้นทางที่สั้นที่สุดโดยไม่ต้องใช้แผนที่". Lecture Notes in Computer Science . Proc. 16th ICALP. Vol. 372. Springer-Verlag . pp. 610– 620.
^ Alex Fabrikant และ Christos Papadimitriouความซับซ้อนของพลวัตเกม: การแกว่งของ BGP สมดุลของซิงค์ และอื่นๆเก็บถาวรเมื่อ 5 กันยายน 2008 ที่ Wayback Machineใน SODA 2008
^ Erik D. Demaine; Robert A. Hearn (23–26 มิถุนายน 2551). ตรรกะข้อจำกัด: กรอบการทำงานที่เป็นเอกภาพสำหรับการจำลองการคำนวณในรูปแบบเกม . เล่มที่. รายงานการประชุมประจำปีครั้งที่ 23 ของ IEEE ว่าด้วยความซับซ้อนของการคำนวณ (Complexity 2008). คอลเลจพาร์ค รัฐแมริแลนด์. หน้า 149–162 .{{cite book}}: CS1 maint: ไม่พบตำแหน่งผู้เผยแพร่ ( ลิงก์ )
^ Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). "ความสมบูรณ์ของ PSPACE ของเกมระบายสีกราฟสองเกม" . วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี . 824– 825: 36– 45. doi : 10.1016/j.tcs.2020.03.022 . S2CID 218777459 .
^ Schaefer, Thomas J. (1978). "เกี่ยวกับความซับซ้อนของเกมข้อมูลสมบูรณ์สองผู้เล่นบางเกม"วารสารวิทยาการคอมพิวเตอร์และระบบ 16 ( 2): 185– 225. doi : 10.1016/0022-0000(78)90045-4 .
^ CH Papadimitriou; JN Tsitsiklis (1987). "ความซับซ้อนของกระบวนการตัดสินใจแบบมาร์คอฟ" (PDF)คณิตศาสตร์ของการวิจัยการดำเนินงาน 12 ( 3): 441– 450. doi : 10.1287/moor.12.3.441 . hdl : 1721.1/2893 .
^ I. Chades; J. Carwardine; TG Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDPs: แนวทางแก้ไขสำหรับการสร้างแบบจำลองปัญหาการจัดการแบบปรับตัวได้ AAAI'12.
^ Casanova, Marco A. และคณะ (1984). " การพึ่งพาการรวมและการมีปฏิสัมพันธ์กับการพึ่งพาเชิงฟังก์ชัน"วารสารวิทยาการคอมพิวเตอร์และระบบ 28 : 29– 59. doi : 10.1016/0022-0000(84)90075-8 .
^ PW Goldberg และCH Papadimitriouและ R. Savani (2011). ความซับซ้อนของวิธีการโฮโมโทปี การเลือกสมดุล และวิธีแก้ปัญหาของเลมเค-ฮาวสัน Proc. 52nd FOCS. IEEE . หน้า 67–76 .
^ Maarten Marx (2007). "ความซับซ้อนของตรรกะเชิงโมดอล". ใน Patrick Blackburn; Johan FAK van Benthem; Frank Wolter (บรรณาธิการ). คู่มือตรรกะเชิงโมดอล . Elsevier. หน้า 170.
^ Lewis, Harry R. (1978). ความซับซ้อนของกรณีที่แก้ได้ของปัญหาการตัดสินใจสำหรับแคลคูลัสเชิงประพจน์ การ ประชุมวิชาการประจำปีครั้งที่ 19 ว่าด้วยพื้นฐานของวิทยาศาสตร์คอมพิวเตอร์ IEEE หน้า 35–47

[1] RA Hearn (2 กุมภาพันธ์ 2548). "Amazons คือ PSPACE-complete". arXiv : cs.CC/0502013 .

[2] Markus Holzer และ Stefan Schwoon (กุมภาพันธ์ 2547) "การประกอบโมเลกุลใน ATOMIX นั้นยาก"วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี 313 ( 3): 447– 462. doi : 10.1016/j.tcs.2002.11.002 .

[3] Aviezri S. Fraenkel (1978). "ความซับซ้อนของหมากรุกบนกระดาน N x N - รายงานเบื้องต้น". การประชุมวิชาการประจำปีครั้งที่ 19 ด้านวิทยาการคอมพิวเตอร์ : 55– 64.

[4] Erik D. Demaine (2009). ความซับซ้อนของปริศนากล้องโทรทรรศน์ไดสันเล่มที่ เกมแห่งโอกาส 3.

[GONC3Hearn-5] Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3 .

[6] Lichtenstein; Sipser (1980). "Go is polynomial-space hard" . Journal of the Association for Computing Machinery . 27 (2): 393– 401. doi : 10.1145/322186.322201 . S2CID 29498352 .

[goladder-7] บันได Go เสร็จสมบูรณ์แล้วใน PSPACE เก็บถาวรเมื่อ 30 กันยายน 2007 ที่ Wayback Machine

[Reisch1980-8] สเตฟาน ไรช์ (1980) "Gobang ist PSPACE-vollstandig (Gomoku คือ PSPACE ที่สมบูรณ์)" แอกต้า อินฟอร์เมติกา . 13 : 59– 66. ดอย : 10.1007/bf00288536 . S2CID 21455572 .

[9] สเตฟาน ไรช์ (1981) "Hex ist PSPACE-vollständig (Hex คือ PSPACE-complete)" แอกต้า อินฟอร์เมติกา (15): 167– 191.

[10] Viglietta, Giovanni (2015). "Lemmings Is PSPACE-Complete" (PDF) . Theoretical Computer Science . 586 : 120– 134. arXiv : 1202.6581 . doi : 10.1016/j.tcs.2015.01.055 .

[AlgorithmicGameTheory-11] Erik D. Demaine; Robert A. Hearn (2009). การเล่นเกมด้วยอัลกอริทึม: ทฤษฎีเกมเชิงผสมแบบอัลกอริทึมเล่มที่ เกมแห่งโอกาส 3.

[Grier2012-12] Grier, Daniel (2013). "การตัดสินผู้ชนะของเกมโพเซตจำกัดใดๆ นั้นเป็น PSPACE-Complete" Automata, Languages, and Programming . Lecture Notes in Computer Science. Vol. 7965. pp. 497– 503. arXiv : 1209.1750 . doi : 10.1007/978-3-642-39206-1_42 . ISBN 978-3-642-39205-4. S2CID 13129445 .

[13] Shigeki Iwata และ Takumi Kasai (1994). "เกม Othello บนกระดาน n*n สมบูรณ์แบบ PSPACE" . วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี . 123 (2): 329– 340. doi : 10.1016/0304-3975(94)90131-7 .

[ncl-14] Hearn ; Demaine (2002). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv : cs.CC/0205005 .

[randshang-15] A. Condon , J. Feigenbaum, C. Lund และ P. Shor , ผู้โต้วาทีแบบสุ่มและความยากของการประมาณฟังก์ชันสุ่ม, SIAM Journal on Computing 26:2 (1997) 369-400

[16] Lampis, Michael; Mitsou, Valia; Sołtys, Karolina (2015). "Scrabble สมบูรณ์แบบ PSPACE" . วารสารการประมวลผลข้อมูล . 23 (3): 284– 292. arXiv : 1201.5298 . doi : 10.2197/ipsjjip.23.284 .

[smb-17] Demaine, Erik D.; Viglietta, Giovanni; Williams, Aaron (มิถุนายน 2016). "Super Mario Bros. ยากกว่า/ง่ายกว่าที่เราคิด" (PDF) . การประชุมนานาชาติว่าด้วยความสนุกกับอัลกอริทึม ครั้งที่ 8 .บทสรุปโดยย่อ: Sabry, Neamat (28 เมษายน 2020). "Super Mario Bros ยาก/ง่ายกว่าที่เราคิด" . Medium .

[18] Gilbert, Lengauer และ RE Tarjan: ปัญหาการโยนก้อนหินนั้นสมบูรณ์ในปริภูมิพหุนาม SIAM Journal on Computing เล่มที่ 9 ฉบับที่ 3 ปี 1980 หน้า 513-524

[19] Philipp Hertel และ Toniann Pitassi : Black-White Pebbling คือ PSPACE-Complete ที่เก็บถาวรเมื่อ 2011-06-08 ที่ Wayback Machine

[pebble-20] Takumi Kasai, Akeo Adachi และ Shigeki Iwata: ประเภทของ Pebble Games และ Complete Problems , SIAM Journal on Computing, เล่มที่ 8, 1979, หน้า 574-586

[WagnerW-21] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k K. Wagner และ G. Wechsung. ความซับซ้อนของการคำนวณ . สำนักพิมพ์D. Reidel , 1986. ISBN 90-277-2146-7

[papadimitriou85games-22] Christos Papadimitriou (1985). "เกมต่อต้านธรรมชาติ" . วารสารวิทยาการคอมพิวเตอร์และระบบ . 31 (2): 288– 301. doi : 10.1016/0022-0000(85)90045-5 .

[SistlaAndClarke-23] APSistla และEdmund M. Clarke (1985). "ความซับซ้อนของตรรกะเชิงเวลาเชิงเส้นแบบประพจน์"วารสารของ ACM 32 ( 3): 733– 749. doi : 10.1145/3828.3837 . S2CID 47217193 .

[integercircuit-24] การประเมินวงจรจำนวนเต็ม

[FOOTNOTEGareyJohnson1979AL3-25] แกรีย์แอนด์จอห์นสัน (1979) , AL3.

[FOOTNOTEGareyJohnson1979AL4-26] แกรีย์แอนด์จอห์นสัน (1979) , AL4.

[FOOTNOTEGareyJohnson1979AL2-27] แกรีย์แอนด์จอห์นสัน (1979) , AL2.

[GalilHierarch-28] Galil, Z.ลำดับชั้นของปัญหาที่สมบูรณ์ใน Acta Informatica 6 (1976), 77-88.

[FOOTNOTEGareyJohnson1979AL1-29] แกรีย์แอนด์จอห์นสัน (1979) , AL1.

[30] LJ Stockmeyerและ AR Meyer. โจทย์ปัญหาที่ต้องใช้เวลาแบบเลขชี้กำลัง ในรายงานการประชุมสัมมนาทฤษฎีการคำนวณครั้งที่ 5 หน้า 1–9, 1973

[31] JE Hopcroft และ JD Ullman.บทนำสู่ทฤษฎีออโตมาตา ภาษา และการคำนวณ ฉบับพิมพ์ครั้งแรก ปี 1979

[D._Kozen_1977-32] D. Kozen. ขอบเขตล่างสำหรับระบบพิสูจน์ตามธรรมชาติ ใน Proc. 18th Symp. on the Foundations of Computer Science, หน้า 254–266, 1977.

[33] ปัญหาของมดของแลงตันเก็บถาวรเมื่อ 27 กันยายน 2007 ที่ Wayback Machineหัวข้อ "ปัญหาของมดของแลงตันแบบสมมาตรทั่วไปนั้นสมบูรณ์แบบ PSPACE" โดย YAMAGUCHI EIJI และ TSUKIJI TATSUIE ในรายงานทางเทคนิคของ IEIC (สถาบันวิศวกรอิเล็กทรอนิกส์ สารสนเทศ และการสื่อสาร )

[34] T. Jiang และ B. Ravikumar. ปัญหา NFA ขั้นต่ำนั้นยาก SIAM Journal on Computing, 22(6):1117–1141, ธันวาคม 1993

[35] S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control , 7 (2): 207–223, มิถุนายน 1964

[36] แบร์นาตสกี, ลาสซโล. "การไม่มีดาวของนิพจน์ปกติคือ PSPACE-Complete" (PDF ) สืบค้นเมื่อ2021-01-13 .

[FOOTNOTEGareyJohnson1979AL12-37] แกรีย์แอนด์จอห์นสัน (1979) , AL12.

[FOOTNOTEGareyJohnson1979AL13-38] แกรีย์แอนด์จอห์นสัน (1979) , AL13.

[FOOTNOTEGareyJohnson1979AL14-39] แกรีย์แอนด์จอห์นสัน (1979) , AL14.

[FOOTNOTEGareyJohnson1979AL16-40] แกรีย์แอนด์จอห์นสัน (1979) , AL16.

[FOOTNOTEGareyJohnson1979AL19-41] แกรีย์แอนด์จอห์นสัน (1979) , AL19.

[FOOTNOTEGareyJohnson1979AL21-42] แกรีย์แอนด์จอห์นสัน (1979) , AL21.

[43] Antonio Lozano และ Jose L. Balcazar. ความซับซ้อนของปัญหาเกี่ยวกับกราฟสำหรับกราฟที่แสดงอย่างกระชับ ใน Manfred Nagl บรรณาธิการ, แนวคิดเชิงทฤษฎีกราฟในวิทยาศาสตร์คอมพิวเตอร์, การประชุมเชิงปฏิบัติการนานาชาติครั้งที่ 15, WG'89, หมายเลข 411 ใน Lecture Notes in Computer Science, หน้า 277–286. Springer-Verlag, 1990.

[44] J. Feigenbaum และ S. Kannan และ MY Vardi และ M. Viswanathan, ความซับซ้อนของปัญหาบนกราฟที่แสดงเป็น OBDD, Chicago Journal of Theoretical Computer Science, เล่ม 5, ฉบับที่ 5, 1999

[45] CH Papadimitriou; M. Yannakakis (1989). "เส้นทางที่สั้นที่สุดโดยไม่ต้องใช้แผนที่". Lecture Notes in Computer Science . Proc. 16th ICALP. Vol. 372. Springer-Verlag . pp. 610– 620.

[46] Alex Fabrikant และ Christos Papadimitriouความซับซ้อนของพลวัตเกม: การแกว่งของ BGP สมดุลของซิงค์ และอื่นๆเก็บถาวรเมื่อ 5 กันยายน 2008 ที่ Wayback Machineใน SODA 2008

[47] Erik D. Demaine; Robert A. Hearn (23–26 มิถุนายน 2551). ตรรกะข้อจำกัด: กรอบการทำงานที่เป็นเอกภาพสำหรับการจำลองการคำนวณในรูปแบบเกม . เล่มที่. รายงานการประชุมประจำปีครั้งที่ 23 ของ IEEE ว่าด้วยความซับซ้อนของการคำนวณ (Complexity 2008). คอลเลจพาร์ค รัฐแมริแลนด์. หน้า 149–162 .{{cite book}}: CS1 maint: ไม่พบตำแหน่งผู้เผยแพร่ ( ลิงก์ )

[48] Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). "ความสมบูรณ์ของ PSPACE ของเกมระบายสีกราฟสองเกม" . วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี . 824– 825: 36– 45. doi : 10.1016/j.tcs.2020.03.022 . S2CID 218777459 .

[49] Schaefer, Thomas J. (1978). "เกี่ยวกับความซับซ้อนของเกมข้อมูลสมบูรณ์สองผู้เล่นบางเกม"วารสารวิทยาการคอมพิวเตอร์และระบบ 16 ( 2): 185– 225. doi : 10.1016/0022-0000(78)90045-4 .

[50] CH Papadimitriou; JN Tsitsiklis (1987). "ความซับซ้อนของกระบวนการตัดสินใจแบบมาร์คอฟ" (PDF)คณิตศาสตร์ของการวิจัยการดำเนินงาน 12 ( 3): 441– 450. doi : 10.1287/moor.12.3.441 . hdl : 1721.1/2893 .

[51] I. Chades; J. Carwardine; TG Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDPs: แนวทางแก้ไขสำหรับการสร้างแบบจำลองปัญหาการจัดการแบบปรับตัวได้ AAAI'12.

[52] Casanova, Marco A. และคณะ (1984). " การพึ่งพาการรวมและการมีปฏิสัมพันธ์กับการพึ่งพาเชิงฟังก์ชัน"วารสารวิทยาการคอมพิวเตอร์และระบบ 28 : 29– 59. doi : 10.1016/0022-0000(84)90075-8 .

[53] PW Goldberg และCH Papadimitriouและ R. Savani (2011). ความซับซ้อนของวิธีการโฮโมโทปี การเลือกสมดุล และวิธีแก้ปัญหาของเลมเค-ฮาวสัน Proc. 52nd FOCS. IEEE . หน้า 67–76 .

[54] Maarten Marx (2007). "ความซับซ้อนของตรรกะเชิงโมดอล". ใน Patrick Blackburn; Johan FAK van Benthem; Frank Wolter (บรรณาธิการ). คู่มือตรรกะเชิงโมดอล . Elsevier. หน้า 170.

[55] Lewis, Harry R. (1978). ความซับซ้อนของกรณีที่แก้ได้ของปัญหาการตัดสินใจสำหรับแคลคูลัสเชิงประพจน์ การ ประชุมวิชาการประจำปีครั้งที่ 19 ว่าด้วยพื้นฐานของวิทยาศาสตร์คอมพิวเตอร์ IEEE หน้า 35–47

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]

44 ] หรือ

[ 45 ]

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[

[

รายชื่อปัญหา PSPACE ที่สมบูรณ์

เกมและปริศนา

ตรรกะ

แคลคูลัสแลมบ์ดา

ออโตมาตาและทฤษฎีภาษา

ทฤษฎีวงจร

ทฤษฎีออโตมาตา

ภาษาทางการ

ทฤษฎีกราฟ

คนอื่น

ดูเพิ่มเติม

หมายเหตุ

ข้อมูลสำคัญจากบทความ