List of PSPACE-complete problems
From Wikipedia, the free encyclopedia
Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive.
This list is incomplete; you can help by expanding it.
Contents |
[edit] Games and puzzles
Amazons · Atomix · Generalized Geography · Generalized Gomoku [1] · Generalized hex · Reversi · Rush Hour · Finding optimal play in Mahjong solitaire · Sokoban
[edit] Logic
[edit] Miscellaneous
[edit] Automata and language theory
[edit] Automata theory
Linear bounded automaton acceptance · Non-erasing stack automaton acceptance [2] · Two-way finite state automaton non-emptiness? · Quasi-realtime automaton acceptance? · Finite state automata intersection[3] [4] [5]
[edit] Formal languages
Regular expression inequivalence? · Regular grammar inequivalence? · Context-sensitive language membership
[edit] See also
[edit] References
- ^ Stefan Reisch, Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete). Acta Informatica, 13:5966, 1980.
- ^ Hopcroft, Motwani, and Ullman: Introduction to Automata Theory, Languages, and Computation (first or second edition)
- ^ D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
- ^ M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
- ^ K.-J. Lange and P. Rossmanith. The emptiness problem for intersections of regular languages. In I. Havel, editor, Proc. of the 17th Conf. on Mathematical Foundations of Computer Science, number 629 in LNCS, pages 346–354. Springer-Verlag, 1992.
