Content deleted Content added
m →Automata theory: fix common MOS:REFSPACE spacing errors, replaced: /ref> <ref → /ref><ref |
|||
| (31 intermediate revisions by 21 users not shown) | |||
Line 1:
{{
{{dynamic list}}
{{use mdy dates|cs1-dates=ly|date=September 2022}}
Here are some of the more commonly known problems that are [[PSPACE-complete]] when expressed as [[decision problem]]s. This list is in no way comprehensive.
Line 7 ⟶ 8:
[[Generalized game|Generalized]] versions of:
{{div col |colwidth=18em}}
* [[Amazons (game)|Amazons]]<ref>{{cite arXiv | author = R. A. Hearn | author-link=Bob Hearn | title = Amazons is PSPACE-complete | date = 2005-02-02 | eprint = cs.CC/0502013 }}</ref>
* [[Atomix (computer game)|Atomix]]<ref>{{Cite journal | author = Markus Holzer and Stefan Schwoon | title = Assembling molecules in ATOMIX is hard | journal = Theoretical Computer Science | volume = 313 | issue = 3 |date=February 2004 | pages = 447–462 | doi = 10.1016/j.tcs.2002.11.002| doi-access = free }}</ref>
* [[Checkers]]
* [[Dyson Telescope Game]]<ref>{{cite book | author=Erik D. Demaine | title=The complexity of the Dyson Telescope Puzzle | volume = Games of No Chance 3 | year=2009}}</ref>
* [[TipOver|Cross Purposes]]<ref name="GONC3Hearn">{{cite journal | author = Robert A. Hearn | author-link = Bob Hearn | title=Amazons, Konane, and Cross Purposes are PSPACE-complete |
* [[Generalized geography|Geography]]
* Two-player game version of [[Instant Insanity]]
* [[Ko rule|Ko]]-free [[Go (game)|Go]]<ref>{{cite journal | author = Lichtenstein | author2 = Sipser | title = Go is polynomial-space hard | journal = Journal of the Association for Computing Machinery | volume = 27 | issue=2 | pages = 393–401 | year = 1980 | doi = 10.1145/322186.322201| s2cid = 29498352 | doi-access = free }}</ref>
* [[Ladder (Go)|Ladder capturing in Go]]<ref name=goladder>[http://homepages.cwi.nl/~tromp/lad.ps Go ladders are PSPACE-complete] {{webarchive|url=https://web.archive.org/web/20070930044618/http://homepages.cwi.nl/~tromp/lad.ps |date=2007-09-30 }}</ref>
* [[m,n,k-game|Gomoku]]<ref name="Reisch1980">{{cite journal | author = Stefan Reisch | title = Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete) | journal = Acta Informatica | volume = 13 | pages = 59–66 | year = 1980 | doi=10.1007/bf00288536| s2cid = 21455572 }}</ref>
* [[Hex (board game)|Hex]]<ref>{{cite journal | author = Stefan Reisch | title = Hex ist PSPACE-vollständig (Hex is PSPACE-complete) | journal = Acta
* [[Konane]]<ref name="GONC3Hearn"/>
* [[Lemmings (video game)|Lemmings]]<ref>{{cite journal|last1=Viglietta|first1=Giovanni|title=Lemmings Is PSPACE-Complete|journal=Theoretical Computer Science|date=2015|volume=586|pages=120–134 |url=http://giovanniviglietta.com/papers/lemmings2.pdf|doi=10.1016/j.tcs.2015.01.055 |arxiv=1202.6581 |doi-access=free}}</ref>
* [[Node Kayles]]<ref name="AlgorithmicGameTheory">{{cite book | author=Erik D. Demaine | author2=Robert A. Hearn | author2-link = Bob Hearn | title=Playing Games with Algorithms: Algorithmic Combinatorial Game Theory | volume = Games of No Chance 3 | year=2009 | url=http://erikdemaine.org/papers/AlgGameTheory_GONC3/}}</ref>
* [[Poset Game]]<ref name="Grier2012">{{cite book | last = Grier | first = Daniel | chapter = Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete | arxiv = 1209.1750
* [[Reversi]]<ref>{{cite journal | author = Shigeki Iwata and Takumi Kasai | title = The Othello game on an n*n board is PSPACE-complete | journal = Theoretical Computer Science | volume = 123 | issue = 2 | year = 1994 | pages = 329–340 | doi = 10.1016/0304-3975(94)90131-7| doi-access = free }}</ref>
* [[River Crossing]]<ref name=ncl/>
* [[Rush Hour (board game)|Rush Hour]]<ref name=ncl>{{cite arXiv|eprint=cs.CC/0205005|author1=Hearn|author1-link=Bob Hearn|author2=Demaine|title=PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation |year=2002}}</ref>
* Finding optimal play in [[Mahjong solitaire]]<ref name=randshang>[[Anne Condon|A. Condon]], J. Feigenbaum, C. Lund, and [[Peter Shor|P. Shor]], Random debaters and the hardness of approximating stochastic functions, [[SIAM Journal on Computing]] 26:2 (1997) 369-400.</ref>
* [[Scrabble]]<ref>{{ cite journal | first1=Michael | last1=Lampis | first2 = Valia | last2 = Mitsou | first3 = Karolina | last3 = Sołtys | title = Scrabble is PSPACE-complete | journal = Journal of Information Processing | date = 2015 | url = https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_284/_article }}</ref>
* [[Sokoban]]<ref name=ncl/>
* [[Super Mario Bros.]]<ref name=smb>{{cite journal|
* Black [[Pebble game]]<ref>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.</ref>
* Black-White [[Pebble game]]<ref>Philipp Hertel and [[Toniann Pitassi]]: [http://www.cs.toronto.edu/~philipp/pages/papers/BWPebbling.pdf Black-White Pebbling is PSPACE-Complete] {{webarchive|url=https://web.archive.org/web/20110608053819/http://www.cs.toronto.edu/~philipp/pages/papers/BWPebbling.pdf |date=2011-06-08 }}</ref>
Line 32 ⟶ 35:
* One-player [[pebble game]]<ref name=pebble/>
* Token on [[acyclic directed graph]] games:<ref name="AlgorithmicGameTheory"/>
{{div col end}}
Line 53 ⟶ 50:
* [[First-order theory]] of [[binary string]]s under [[lexicographic order]]ing<ref name="WagnerW"/>
* [[First-order theory]] of a finite [[Boolean algebra (structure)|Boolean algebra]]<ref name="WagnerW"/>
* Stochastic satisfiability<ref name=papadimitriou85games>{{cite journal|author=Christos Papadimitriou |title=Games against Nature |doi=10.1016/0022-0000(85)90045-5 | journal=Journal of Computer and System Sciences
* [[Linear temporal logic]] satisfiability and model checking<ref name="SistlaAndClarke">{{cite journal|author=A.P.Sistla and [[Edmund M. Clarke]]|title=The complexity of propositional linear temporal logics|journal=Journal of the ACM|volume=32|issue=3|year=1985|doi=10.1145/3828.3837|pages=733–749|s2cid=47217193 |doi-access=free}}</ref>
{{div col end}}
Line 63 ⟶ 60:
=== Circuit theory ===
[[Integer circuit]] evaluation<ref name=integercircuit>[
=== Automata theory ===
{{div col |colwidth=36em}}
* Word problem for [[linear bounded automata]]
* Word problem for [[quasi-realtime automata]]
* [[Emptiness problem]] for a nondeterministic [[two-way finite state automaton]]{{sfnp|Garey|Johnson|1979|loc=AL2}}<ref name = GalilHierarch>Galil, Z. ''Hierarchies of Complete Problems''. In Acta Informatica 6 (1976), 77-88.
* Equivalence problem for [[Nondeterministic finite automaton|nondeterministic finite automata]]{{sfnp|Garey|Johnson|1979|loc=AL1}}<ref>[[Larry Stockmeyer|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.
* Word problem and emptiness problem for non-erasing [[stack automaton|stack automata]]<ref>J. E. Hopcroft and J. D. Ullman. [[Introduction to Automata Theory, Languages, and Computation]], first edition, 1979.</ref>
* [[
<!-- the original reference to Kozen should suffice, no?...
<ref>M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.</ref>
-->
* A generalized version of [[Langton's Ant]]<ref>[http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php Langton's Ant problem] {{webarchive|url=https://web.archive.org/web/20070927225749/http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php |date=2007-09-27 }}, "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]])</ref>
Line 84 ⟶ 81:
* Word problem for [[context-sensitive language]]<ref>S.-Y. Kuroda, "Classes of languages and linear-bounded automata", ''Information and Control'', '''7'''(2): 207–223, June 1964.</ref>
* Intersection emptiness for an unbounded number of [[regular language]]s <ref name="D. Kozen 1977"/>
* Regular Expression
* [[Equivalence problem]] for [[regular expression]]s<ref name = WagnerW/>
* [[Emptiness problem]] for [[regular expression]]s with intersection.<ref name = WagnerW/>
* [[Equivalence problem]] for star-free [[regular expression]]s with squaring.<ref name = WagnerW/>
* Covering for [[linear grammar]]s
* Structural equivalence for [[linear grammar]]s
* [[Equivalence problem]] for [[Regular grammar]]s
* [[Emptiness problem]] for [[ET0L]] grammars
* Word problem for [[ET0L]] grammars
* [[Tree transducer language]] membership problem for top down finite-state tree transducers
{{div col end}}
== Graph theory ==
{{div col |colwidth=
* succinct versions of many graph problems, with graphs represented as Boolean circuits,<ref>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,
** s-t reachability problem for succinct graphs. This is essentially the same as the simplest plan existence problem in [[automated planning and scheduling]].
** planarity of succinct graphs
Line 104 ⟶ 101:
** connectedness of succinct graphs
** existence of Eulerian paths in a succinct graph
* Bounded two-player Constraint Logic<ref name="AlgorithmicGameTheory"/>▼
* [[Canadian traveller problem]].<ref>{{cite conference | author=C.H. Papadimitriou |author2=M. Yannakakis | title=Shortest paths without a map | conference=Proc. 16th ICALP | book-title=Lecture Notes in Computer Science | volume=372 | publisher=[[Springer-Verlag]] | year=1989 | pages=610–620 }}</ref>
* Determining whether routes selected by the [[Border Gateway Protocol]] will eventually converge to a stable state for a given set of path preferences<ref>Alex Fabrikant and [[Christos Papadimitriou]]. [http://www.cs.berkeley.edu/~alexf/papers/fp08.pdf The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond] {{webarchive|url=https://web.archive.org/web/20080905124129/http://www.cs.berkeley.edu/~alexf/papers/fp08.pdf |date=2008-09-05 }}. In SODA 2008.</ref>
* Dynamic graph reliability.<ref name=papadimitriou85games/>▼
* Deterministic [[constraint logic]] (unbounded)<ref>{{cite book
|
| author2 = Robert A. Hearn | author2-link = Bob Hearn
| title = Constraint Logic: A Uniform Framework for Modeling Computation as Games
| volume = Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008)
Line 116 ⟶ 114:
| pages = 149–162
}}</ref>
▲* Dynamic graph reliability.<ref name=papadimitriou85games/>
* [[Graph coloring game]]<ref>{{cite journal|last1=Costa|first1=Eurinardo|last2=Pessoa|first2=Victor Lage |last3=Soares|first3=Ronan|last4=Sampaio|first4=Rudini|date=2020|title=PSPACE-completeness of two graph coloring games |journal=Theoretical Computer Science|volume=824-825|pages=36–45 |doi=10.1016/j.tcs.2020.03.022 |s2cid=218777459|doi-access=free}}</ref>
* [[Kayles|Node Kayles game and clique-forming game]]:<ref>{{cite journal|last1=Schaefer|first1=Thomas J. |date=1978|title=On the complexity of some two-person perfect-information games|journal=Journal of Computer and System Sciences|volume=16|issue=2 |pages=185–225|doi=10.1016/0022-0000(78)90045-4|doi-access=free}}</ref> two players alternately select vertices and the induced subgraph must be an independent set (resp. clique). The last to play wins.
* Nondeterministic Constraint Logic (unbounded)<ref name="AlgorithmicGameTheory"/>
▲* Bounded two-player Constraint Logic<ref name="AlgorithmicGameTheory"/>
{{div col end}}
== Others ==
{{div col |colwidth=36em}}
* Finite horizon POMDPs (Partially Observable Markov Decision Processes).<ref>{{cite journal | author=C.H. Papadimitriou |author2=J.N. Tsitsiklis | title=The complexity of Markov Decision Processes | journal= Mathematics of Operations Research| volume=12 | number=3 | year=1987| pages=441–450 | doi=10.1287/moor.12.3.441| url=http://dspace.mit.edu/bitstream/1721.1/2893/1/P-1479-13685602.pdf|hdl=1721.1/2893 | hdl-access=free }}</ref>
* Hidden Model MDPs (hmMDPs).<ref>{{cite conference | author=I. Chades |author2=J. Carwardine |author3=T.G. Martin |author4=S. Nicol |author5=R. Sabbadin |author6=O. Buffet | title=MOMDPs: A Solution for Modelling Adaptive Management Problems | conference=AAAI'12 | year=2012}}</ref>
* Dynamic Markov process.<ref name=papadimitriou85games/>
* Detection of inclusion dependencies in a relational database<ref>{{cite journal |
* Computation of any [[Nash equilibrium]] of a 2-player [[normal-form game]], that may be obtained via the [[Lemke–Howson algorithm]].<ref>{{cite conference | author= P.W. Goldberg and [[Christos Papadimitriou|C.H. Papadimitriou]] and R. Savani | title=The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions | conference=Proc. 52nd FOCS | publisher=[[IEEE]] | year=2011 | pages=67–76 }}</ref>
* The Corridor Tiling Problem: given a set of [[Wang tile]]s, a chosen tile <math>T_0</math> and a width <math>n</math> given in unary notation, is there any height <math>m</math> such that an <math>n\times m</math> rectangle can be tiled such that all the border tiles are <math>T_0</math>?<ref>{{cite encyclopedia |author= Maarten Marx | title=Complexity of Modal Logic | encyclopedia=Handbook of Modal Logic |editor1=Patrick Blackburn |editor2= Johan F.A.K. van Benthem|editor3 = Frank Wolter| publisher=Elsevier |year=2007 |page=170}}</ref><ref>{{cite conference| title= Complexity of solvable cases of the decision problem for the predicate calculus| author=Lewis, Harry R.| conference=19th Annual Symposium on Foundations of Computer Science| pages= 35–47| year= 1978| publisher=IEEE}}</ref>
Line 139:
== References ==
*{{cite book
|
|
| author-link = Michael Garey
|
| title = Computers and Intractability: A Guide to the Theory of NP-Completeness
| year = 1979
Line 153:
* [https://arxiv.org/abs/math/9409225 The Complexity of Approximating PSPACE-complete problems for hierarchical specifications]
[[Category:
[[Category:PSPACE-complete problems| ]]
[[Category:Lists of problems]]
| |||