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

Quantified boolean formulas

[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

  1. ^ Stefan Reisch, Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete). Acta Informatica, 13:5966, 1980.
  2. ^ Hopcroft, Motwani, and Ullman: Introduction to Automata Theory, Languages, and Computation (first or second edition)
  3. ^ D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
  4. ^ M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
  5. ^ 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.
Retrieved from "http://en.wikipedia.org../../../l/i/s/List_of_PSPACE-complete_problems_5405.html"