List of PSPACE-complete problems

<h2 id="games-and-puzzles">Games and puzzles</h2>
<a href="/facts/Generalized_game/dY2tP9pn">Generalized</a> versions of:

<ul><li><a href="/facts/Amazons_(game)/bcEP1Wxr">Amazons</a><a class="footnote-ref" id="fnref:1" href="#fn:1">1</a></li>
<li><a href="/facts/Atomix_(computer_game)/SpYtrUUl">Atomix</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></li>
<li><a href="/facts/Checkers/zrzKMsyu">Checkers</a> if a draw is forced after a polynomial number of non-jump moves<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></li>
<li>Dyson Telescope Game<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>Cross Purposes<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li><a href="/facts/Generalized_geography/GuawoTHh">Geography</a></li>
<li>Two-player game version of <a href="/facts/Instant_Insanity/lacpVjQM">Instant Insanity</a></li>
<li><a href="/facts/Ko_rule/6m1mEsMI">Ko</a>-free <a href="/facts/Go_(game)/1fKhemww">Go</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li><a href="/facts/Ladder_(Go)/akoF34Yp">Ladder capturing in Go</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li>
<li><a href="/facts/M%2cn%2ck-game/Dt0LNcb4">Gomoku</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li><a href="/facts/Hex_(board_game)/9qmGgQkt">Hex</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li>
<li><a href="/facts/Konane/l7LY1pMj">Konane</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a></li>
<li><a href="/facts/Lemmings_(video_game)/9T2Q9x64">Lemmings</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li>
<li>Node Kayles<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a></li>
<li><a href="/facts/Poset_Game/SlMHvoMM">Poset Game</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a></li>
<li><a href="/facts/Reversi/Bxp4jHAw">Reversi</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a></li>
<li><a href="/facts/River_Crossing/NfDUFT6X">River Crossing</a><a class="footnote-ref" id="fnref:15" href="#fn:15">15</a></li>
<li><a href="/facts/Rush_Hour_(board_game)/d6y9TSXv">Rush Hour</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a></li>
<li>Finding optimal play in <a href="/facts/Mahjong_solitaire/bTpXzjF4">Mahjong solitaire</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a></li>
<li><a href="/facts/Scrabble/BxpF5qNv">Scrabble</a><a class="footnote-ref" id="fnref:18" href="#fn:18">18</a></li>
<li><a href="/facts/Sokoban/T1G50XgG">Sokoban</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a></li>
<li><a href="/facts/Super_Mario_Bros./ryoTeTg7">Super Mario Bros.</a><a class="footnote-ref" id="fnref:20" href="#fn:20">20</a></li>
<li>Black <a href="/facts/Pebble_game/9tMGXPMg">Pebble game</a><a class="footnote-ref" id="fnref:21" href="#fn:21">21</a></li>
<li>Black-White <a href="/facts/Pebble_game/9tMGXPMg">Pebble game</a><a class="footnote-ref" id="fnref:22" href="#fn:22">22</a></li>
<li><a href="/facts/Acyclic_directed_graph/k6zq1os9">Acyclic</a> <a href="/facts/Pebble_game/9tMGXPMg">pebble game</a><a class="footnote-ref" id="fnref:23" href="#fn:23">23</a></li>
<li>One-player <a href="/facts/Pebble_game/9tMGXPMg">pebble game</a><a class="footnote-ref" id="fnref:24" href="#fn:24">24</a></li>
<li>Token on <a href="/facts/Acyclic_directed_graph/k6zq1os9">acyclic directed graph</a> games:<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a></li></ul>

<h2 id="logic">Logic</h2>

<ul><li><a href="/facts/Quantified_boolean_formula/aAl09lCF">Quantified boolean formulas</a></li>
<li><a href="/facts/First-order_logic/lcISqWIg">First-order logic</a> of <a href="/facts/Equality_(mathematics)/AQCuumLg">equality</a><a class="footnote-ref" id="fnref:26" href="#fn:26">26</a></li>
<li>Provability in <a href="/facts/Intuitionistic_logic/zI7ulCnM">intuitionistic propositional logic</a></li>
<li>Satisfaction in <a href="/facts/Modal_logic/I7uXvYYT">modal logic S4</a><a class="footnote-ref" id="fnref:27" href="#fn:27">27</a></li>
<li><a href="/facts/First-order_theory/lcISqWIg">First-order theory</a> of the <a href="/facts/Natural_number/u65og8JE">natural numbers</a> under the successor operation<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a></li>
<li><a href="/facts/First-order_theory/lcISqWIg">First-order theory</a> of the <a href="/facts/Natural_number/u65og8JE">natural numbers</a> under the standard order<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a></li>
<li><a href="/facts/First-order_theory/lcISqWIg">First-order theory</a> of the <a href="/facts/Integer/PUwwrawx">integers</a> under the standard order<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a></li>
<li><a href="/facts/First-order_theory/lcISqWIg">First-order theory</a> of <a href="/facts/Well-ordered_set/GrWEBWlW">well-ordered sets</a><a class="footnote-ref" id="fnref:31" href="#fn:31">31</a></li>
<li><a href="/facts/First-order_theory/lcISqWIg">First-order theory</a> of <a href="/facts/Binary_string/4ChJu5WS">binary strings</a> under <a href="/facts/Lexicographic_order/xQANy8Br">lexicographic ordering</a><a class="footnote-ref" id="fnref:32" href="#fn:32">32</a></li>
<li><a href="/facts/First-order_theory/lcISqWIg">First-order theory</a> of a finite <a href="/facts/Boolean_algebra_(structure)/cHbo65jm">Boolean algebra</a><a class="footnote-ref" id="fnref:33" href="#fn:33">33</a></li>
<li>Stochastic satisfiability<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a></li>
<li><a href="/facts/Linear_temporal_logic/Gh5yxXK7">Linear temporal logic</a> satisfiability and model checking<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a></li></ul>

<h2 id="lambda-calculus">Lambda calculus</h2>
<a href="/facts/Type_inhabitation_problem/XFjqj32o">Type inhabitation problem</a> for simply typed lambda calculus

<h2 id="automata-and-language-theory">Automata and language theory</h2>
<h3>Circuit theory</h3>
<a href="/facts/Integer_circuit/LfTFBjHq">Integer circuit</a> evaluation<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a>

<h3>Automata theory</h3>

<ul><li>Word problem for <a href="/facts/Linear_bounded_automata/l0ybKuwE">linear bounded automata</a><a class="footnote-ref" id="fnref:37" href="#fn:37">37</a></li>
<li>Word problem for quasi-realtime automata<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a></li>
<li><a href="/facts/Emptiness_problem/ho61ybCq">Emptiness problem</a> for a nondeterministic <a href="/facts/Two-way_finite_state_automaton/0JQRrb4E">two-way finite state automaton</a><a class="footnote-ref" id="fnref:39" href="#fn:39">39</a><a class="footnote-ref" id="fnref:40" href="#fn:40">40</a></li>
<li>Equivalence problem for <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">nondeterministic finite automata</a><a class="footnote-ref" id="fnref:41" href="#fn:41">41</a><a class="footnote-ref" id="fnref:42" href="#fn:42">42</a></li>
<li>Word problem and emptiness problem for non-erasing <a href="/facts/Stack_automaton/kEPRC70F">stack automata</a><a class="footnote-ref" id="fnref:43" href="#fn:43">43</a></li>
<li><a href="/facts/Intersection_non-emptiness_problem/bJKBuVV0">Emptiness of intersection of an unbounded number of deterministic finite automata</a><a class="footnote-ref" id="fnref:44" href="#fn:44">44</a></li>
<li>A generalized version of <a href="/facts/Langton%2527s_Ant/KLgo2nNe">Langton's Ant</a><a class="footnote-ref" id="fnref:45" href="#fn:45">45</a></li>
<li>Minimizing <a href="/facts/Nondeterministic_finite_automata/fW600oAl">nondeterministic finite automata</a><a class="footnote-ref" id="fnref:46" href="#fn:46">46</a></li></ul>

<h3>Formal languages</h3>

<ul><li>Word problem for <a href="/facts/Context-sensitive_language/01l81plI">context-sensitive language</a><a class="footnote-ref" id="fnref:47" href="#fn:47">47</a></li>
<li>Intersection emptiness for an unbounded number of <a href="/facts/Regular_language/ahxw67T1">regular languages</a> <a class="footnote-ref" id="fnref:48" href="#fn:48">48</a></li>
<li>Regular Expression Star-Freeness <a class="footnote-ref" id="fnref:49" href="#fn:49">49</a></li>
<li><a href="/facts/Equivalence_problem/01tMSYWs">Equivalence problem</a> for <a href="/facts/Regular_expression/KFL3veHX">regular expressions</a><a class="footnote-ref" id="fnref:50" href="#fn:50">50</a></li>
<li><a href="/facts/Emptiness_problem/ho61ybCq">Emptiness problem</a> for <a href="/facts/Regular_expression/KFL3veHX">regular expressions</a> with intersection.<a class="footnote-ref" id="fnref:51" href="#fn:51">51</a></li>
<li><a href="/facts/Equivalence_problem/01tMSYWs">Equivalence problem</a> for star-free <a href="/facts/Regular_expression/KFL3veHX">regular expressions</a> with squaring.<a class="footnote-ref" id="fnref:52" href="#fn:52">52</a></li>
<li>Covering for <a href="/facts/Linear_grammar/Xus2qq8X">linear grammars</a><a class="footnote-ref" id="fnref:53" href="#fn:53">53</a></li>
<li>Structural equivalence for <a href="/facts/Linear_grammar/Xus2qq8X">linear grammars</a><a class="footnote-ref" id="fnref:54" href="#fn:54">54</a></li>
<li><a href="/facts/Equivalence_problem/01tMSYWs">Equivalence problem</a> for <a href="/facts/Regular_grammar/EFCPJB9K">Regular grammars</a><a class="footnote-ref" id="fnref:55" href="#fn:55">55</a></li>
<li><a href="/facts/Emptiness_problem/ho61ybCq">Emptiness problem</a> for ET0L grammars<a class="footnote-ref" id="fnref:56" href="#fn:56">56</a></li>
<li>Word problem for ET0L grammars<a class="footnote-ref" id="fnref:57" href="#fn:57">57</a></li>
<li>Tree transducer language membership problem for top down finite-state tree transducers<a class="footnote-ref" id="fnref:58" href="#fn:58">58</a></li></ul>

<h2 id="graph-theory">Graph theory</h2>

<ul><li>succinct versions of many graph problems, with graphs represented as Boolean circuits,<a class="footnote-ref" id="fnref:59" href="#fn:59">59</a> ordered <a href="/facts/Binary_decision_diagram/977o5E7L">binary decision diagrams</a><a class="footnote-ref" id="fnref:60" href="#fn:60">60</a> or other related representations:
<ul><li>s-t reachability problem for succinct graphs. This is essentially the same as the simplest plan existence problem in <a href="/facts/Automated_planning_and_scheduling/VL1TcrmD">automated planning and scheduling</a>.</li>
<li>planarity of succinct graphs</li>
<li>acyclicity of succinct graphs</li>
<li>connectedness of succinct graphs</li>
<li>existence of Eulerian paths in a succinct graph</li></ul></li>
<li>Bounded two-player Constraint Logic<a class="footnote-ref" id="fnref:61" href="#fn:61">61</a></li>
<li><a href="/facts/Canadian_traveller_problem/TNvAQ5JT">Canadian traveller problem</a>.<a class="footnote-ref" id="fnref:62" href="#fn:62">62</a></li>
<li>Determining whether routes selected by the <a href="/facts/Border_Gateway_Protocol/XfYgBzW3">Border Gateway Protocol</a> will eventually converge to a stable state for a given set of path preferences<a class="footnote-ref" id="fnref:63" href="#fn:63">63</a></li>
<li>Deterministic constraint logic (unbounded)<a class="footnote-ref" id="fnref:64" href="#fn:64">64</a></li>
<li>Dynamic graph reliability.<a class="footnote-ref" id="fnref:65" href="#fn:65">65</a></li>
<li><a href="/facts/Graph_coloring_game/m7oue8TC">Graph coloring game</a><a class="footnote-ref" id="fnref:66" href="#fn:66">66</a></li>
<li><a href="/facts/Kayles/SEfTlKEn">Node Kayles game and clique-forming game</a>:<a class="footnote-ref" id="fnref:67" href="#fn:67">67</a> two players alternately select vertices and the induced subgraph must be an independent set (resp. clique). The last to play wins.</li>
<li>Nondeterministic Constraint Logic (unbounded)<a class="footnote-ref" id="fnref:68" href="#fn:68">68</a></li></ul>

<h2 id="others">Others</h2>

<ul><li>Finite horizon POMDPs (Partially Observable Markov Decision Processes).<a class="footnote-ref" id="fnref:69" href="#fn:69">69</a></li>
<li>Hidden Model MDPs (hmMDPs).<a class="footnote-ref" id="fnref:70" href="#fn:70">70</a></li>
<li>Dynamic Markov process.<a class="footnote-ref" id="fnref:71" href="#fn:71">71</a></li>
<li>Detection of inclusion dependencies in a relational database<a class="footnote-ref" id="fnref:72" href="#fn:72">72</a></li>
<li>Computation of any <a href="/facts/Nash_equilibrium/l74xzIHd">Nash equilibrium</a> of a 2-player <a href="/facts/Normal-form_game/1zxxyHC0">normal-form game</a>, that may be obtained via the <a href="/facts/Lemke%25E2%2580%2593Howson_algorithm/XhsT2zCl">Lemke–Howson algorithm</a>.<a class="footnote-ref" id="fnref:73" href="#fn:73">73</a></li>
<li>The Corridor Tiling Problem: given a set of <a href="/facts/Wang_tile/639AJElj">Wang tiles</a>, a chosen tile 
 
 
 
 
 T
 
 0
 
 
 
 
 {\displaystyle T_{0}}
 
 and a width 
 
 
 
 n
 
 
 {\displaystyle n}
 
 given in unary notation, is there any height 
 
 
 
 m
 
 
 {\displaystyle m}
 
 such that an 
 
 
 
 n
 ×
 m
 
 
 {\displaystyle n\times m}
 
 rectangle can be tiled such that all the border tiles are 
 
 
 
 
 T
 
 0
 
 
 
 
 {\displaystyle T_{0}}
 
?<a class="footnote-ref" id="fnref:74" href="#fn:74">74</a><a class="footnote-ref" id="fnref:75" href="#fn:75">75</a></li></ul>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/List_of_NP-complete_problems/pmR9Dlym">List of NP-complete problems</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Michael_Garey/xuSLYs90">Garey, M.R.</a>; <a href="/facts/David_S._Johnson/kGSBxucb">Johnson, D.S.</a> (1979). <a href="/facts/Computers_and_Intractability%3a_A_Guide_to_the_Theory_of_NP-Completeness/04FE56Ss">Computers and Intractability: A Guide to the Theory of NP-Completeness</a>. New York: W.H. Freeman. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-7167-1045-5.</li>
<li><a href="http://www.ics.uci.edu/~eppstein/cgt/hard.html">Eppstein's page on computational complexity of games</a></li>
<li><a href="https://arxiv.org/abs/math/9409225">The Complexity of Approximating PSPACE-complete problems for hierarchical specifications</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">R. A. Hearn (February 2, 2005). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013. <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Markus Holzer and Stefan Schwoon (February 2004). "Assembling molecules in ATOMIX is hard". Theoretical Computer Science. 313 (3): 447–462. doi:10.1016/j.tcs.2002.11.002. <a href="https://doi.org/10.1016%2Fj.tcs.2002.11.002" target="_blank">https://doi.org/10.1016%2Fj.tcs.2002.11.002</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Aviezri S. Fraenkel (1978). "The complexity of checkers on an N x N board - preliminary report". Proceedings of the 19th Annual Symposium on Computer Science: 55–64. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Erik D. Demaine (2009). The complexity of the Dyson Telescope Puzzle. Vol. Games of No Chance 3. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3. <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="https://doi.org/10.1145%2F322186.322201" target="_blank">https://doi.org/10.1145%2F322186.322201</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Go ladders are PSPACE-complete Archived 2007-09-30 at the Wayback Machine <a href="http://homepages.cwi.nl/~tromp/lad.ps" target="_blank">http://homepages.cwi.nl/~tromp/lad.ps</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)". Acta Informatica. 13: 59–66. doi:10.1007/bf00288536. S2CID 21455572. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Informatica (15): 167–191. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3. <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">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 href="http://giovanniviglietta.com/papers/lemmings2.pdf" target="_blank">http://giovanniviglietta.com/papers/lemmings2.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3. <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Grier, Daniel (2013). "Deciding the Winner of an Arbitrary Finite Poset Game is 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. <a href="978-3-642-39205-4" target="_blank">978-3-642-39205-4</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Shigeki Iwata and Takumi Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theoretical Computer Science. 123 (2): 329–340. doi:10.1016/0304-3975(94)90131-7. <a href="https://doi.org/10.1016%2F0304-3975%2894%2990131-7" target="_blank">https://doi.org/10.1016%2F0304-3975%2894%2990131-7</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">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 href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">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 href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">A. Condon, J. Feigenbaum, C. Lund, and P. Shor, Random debaters and the hardness of approximating stochastic functions, SIAM Journal on Computing 26:2 (1997) 369-400. <a href="/wiki/Anne_Condon" target="_blank">/wiki/Anne_Condon</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Lampis, Michael; Mitsou, Valia; Sołtys, Karolina (2015). "Scrabble is PSPACE-complete". Journal of Information Processing. <a href="https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_284/_article" target="_blank">https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_284/_article</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">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 href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Demaine, Erik D.; Viglietta, Giovanni; Williams, Aaron (June 2016). "Super Mario Bros. Is Harder/Easier than We Thought" (PDF). 8th International Conference of Fun with Algorithms.Lay summary: Sabry, Neamat (April 28, 2020). "Super Mario Bros is Harder/Easier Than We Thought". Medium. <a href="https://dspace.mit.edu/bitstream/handle/1721.1/103079/Supermario%20Demaine.pdf?sequence=1&isAllowed=y" target="_blank">https://dspace.mit.edu/bitstream/handle/1721.1/103079/Supermario%20Demaine.pdf?sequence=1&isAllowed=y</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Gilbert, Lengauer, and R. E. Tarjan: The Pebbling Problem is Complete in Polynomial Space. SIAM Journal on Computing, Volume 9, Issue 3, 1980, pages 513-524. <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Philipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete Archived 2011-06-08 at the Wayback Machine <a href="/wiki/Toniann_Pitassi" target="_blank">/wiki/Toniann_Pitassi</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586. <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586. <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3. <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5. <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">A.P.Sistla and Edmund M. Clarke (1985). "The complexity of propositional linear temporal logics". Journal of the ACM. 32 (3): 733–749. doi:10.1145/3828.3837. S2CID 47217193. <a href="/wiki/Edmund_M._Clarke" target="_blank">/wiki/Edmund_M._Clarke</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Integer circuit evaluation <a href="https://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6911/18589/00856751.pdf" target="_blank">https://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6911/18589/00856751.pdf</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Garey & Johnson (1979), AL3. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Garey & Johnson (1979), AL4. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Garey & Johnson (1979), AL2. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88. <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Garey & Johnson (1979), AL1. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. In Proceedings of the 5th Symposium on Theory of Computing, pages 1–9, 1973. <a href="/wiki/Larry_Stockmeyer" target="_blank">/wiki/Larry_Stockmeyer</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979. <a href="/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation" target="_blank">/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977. <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Langton's Ant problem Archived 2007-09-27 at the Wayback Machine, "Generalized symmetrical Langton's ant problem is PSPACE-complete" by YAMAGUCHI EIJI and TSUKIJI TATSUIE in IEIC Technical Report (Institute of Electronics, Information and Communication Engineers) <a href="http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php" target="_blank">http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993. <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964. <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977. <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Bernátsky, László. "Regular Expression star-freeness is PSPACE-Complete" (PDF). Retrieved 2021-01-13. <a href="http://publicatio.bibl.u-szeged.hu/9528/1/Bernatsky_1997_ActaCybernetica.pdf" target="_blank">http://publicatio.bibl.u-szeged.hu/9528/1/Bernatsky_1997_ActaCybernetica.pdf</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 <a href="/wiki/D._Reidel" target="_blank">/wiki/D._Reidel</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">Garey & Johnson (1979), AL12. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
<li id="fn:54">Garey & Johnson (1979), AL13. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:54" class="footnote-back-ref">↩</a></li>
<li id="fn:55">Garey & Johnson (1979), AL14. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:55" class="footnote-back-ref">↩</a></li>
<li id="fn:56">Garey & Johnson (1979), AL16. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:56" class="footnote-back-ref">↩</a></li>
<li id="fn:57">Garey & Johnson (1979), AL19. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:57" class="footnote-back-ref">↩</a></li>
<li id="fn:58">Garey & Johnson (1979), AL21. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. <a href="#fnref:58" class="footnote-back-ref">↩</a></li>
<li id="fn:59">Antonio Lozano and Jose L. Balcazar. The complexity of graph problems for succinctly represented graphs. In Manfred Nagl, editor, Graph-Theoretic Concepts in Computer Science, 15th International Workshop, WG'89, number 411 in Lecture Notes in Computer Science, pages 277–286. Springer-Verlag, 1990. <a href="#fnref:59" class="footnote-back-ref">↩</a></li>
<li id="fn:60">J. Feigenbaum and S. Kannan and M. Y. Vardi and M. Viswanathan, Complexity of Problems on Graphs Represented as OBDDs, Chicago Journal of Theoretical Computer Science, vol 5, no 5, 1999. <a href="#fnref:60" class="footnote-back-ref">↩</a></li>
<li id="fn:61">Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3. <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:61" class="footnote-back-ref">↩</a></li>
<li id="fn:62">C.H. Papadimitriou; M. Yannakakis (1989). "Shortest paths without a map". Lecture Notes in Computer Science. Proc. 16th ICALP. Vol. 372. Springer-Verlag. pp. 610–620. <a href="/wiki/Springer-Verlag" target="_blank">/wiki/Springer-Verlag</a> <a href="#fnref:62" class="footnote-back-ref">↩</a></li>
<li id="fn:63">Alex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond Archived 2008-09-05 at the Wayback Machine. In SODA 2008. <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:63" class="footnote-back-ref">↩</a></li>
<li id="fn:64">Erik D. Demaine; Robert A. Hearn (June 23–26, 2008). Constraint Logic: A Uniform Framework for Modeling Computation as Games. Vol. Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008). College Park, Maryland. pp. 149–162.{{cite book}}: CS1 maint: location missing publisher (link) <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:64" class="footnote-back-ref">↩</a></li>
<li id="fn:65">Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5. <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:65" class="footnote-back-ref">↩</a></li>
<li id="fn:66">Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). "PSPACE-completeness of two graph coloring games". Theoretical Computer Science. 824–825: 36–45. doi:10.1016/j.tcs.2020.03.022. S2CID 218777459. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:66" class="footnote-back-ref">↩</a></li>
<li id="fn:67">Schaefer, Thomas J. (1978). "On the complexity of some two-person perfect-information games". Journal of Computer and System Sciences. 16 (2): 185–225. doi:10.1016/0022-0000(78)90045-4. <a href="https://doi.org/10.1016%2F0022-0000%2878%2990045-4" target="_blank">https://doi.org/10.1016%2F0022-0000%2878%2990045-4</a> <a href="#fnref:67" class="footnote-back-ref">↩</a></li>
<li id="fn:68">Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3. <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:68" class="footnote-back-ref">↩</a></li>
<li id="fn:69">C.H. Papadimitriou; J.N. Tsitsiklis (1987). "The complexity of Markov Decision Processes" (PDF). Mathematics of Operations Research. 12 (3): 441–450. doi:10.1287/moor.12.3.441. hdl:1721.1/2893. <a href="http://dspace.mit.edu/bitstream/1721.1/2893/1/P-1479-13685602.pdf" target="_blank">http://dspace.mit.edu/bitstream/1721.1/2893/1/P-1479-13685602.pdf</a> <a href="#fnref:69" class="footnote-back-ref">↩</a></li>
<li id="fn:70">I. Chades; J. Carwardine; T.G. Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDPs: A Solution for Modelling Adaptive Management Problems. AAAI'12. <a href="#fnref:70" class="footnote-back-ref">↩</a></li>
<li id="fn:71">Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5. <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:71" class="footnote-back-ref">↩</a></li>
<li id="fn:72">Casanova, Marco A.; et al. (1984). "Inclusion Dependencies and Their Interaction with Functional Dependencies". Journal of Computer and System Sciences. 28: 29–59. doi:10.1016/0022-0000(84)90075-8. <a href="https://doi.org/10.1016%2F0022-0000%2884%2990075-8" target="_blank">https://doi.org/10.1016%2F0022-0000%2884%2990075-8</a> <a href="#fnref:72" class="footnote-back-ref">↩</a></li>
<li id="fn:73">P.W. Goldberg and C.H. Papadimitriou and R. Savani (2011). The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions. Proc. 52nd FOCS. IEEE. pp. 67–76. <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:73" class="footnote-back-ref">↩</a></li>
<li id="fn:74">Maarten Marx (2007). "Complexity of Modal Logic". In Patrick Blackburn; Johan F.A.K. van Benthem; Frank Wolter (eds.). Handbook of Modal Logic. Elsevier. p. 170. <a href="#fnref:74" class="footnote-back-ref">↩</a></li>
<li id="fn:75">Lewis, Harry R. (1978). Complexity of solvable cases of the decision problem for the predicate calculus. 19th Annual Symposium on Foundations of Computer Science. IEEE. pp. 35–47. <a href="#fnref:75" class="footnote-back-ref">↩</a></li>
</ol>

List of PSPACE-complete problems open-in-new

List of PSPACE-complete problems