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

Generalized versions of: Amazons · Atomix · Geography · Gomoku · Hex · Reversi · Rush Hour · Finding optimal play in Mahjong solitaire · Sokoban · Pebble game [1]

[edit] Logic

Quantified boolean formulas · Nondetermistic constraint logic · First-order logic of equality · Satisfaction in intuitionistic propositional logic · Satisfaction in modal logic S4 · Nondetermistic constraint logic · First-order theory of the natural numbers under the standard order · First-order theory of the integers under the standard order · First-order theory of well-ordered sets · First-order theory of binary strings under lexicographic ordering · First-order theory of a finite Boolean algebra

[edit] Lambda calculus

Type inhabitation problem

[edit] Automata and language theory

[edit] Circuit theory

Integer circuit evaluation

[edit] Automata theory

Linear bounded automaton acceptance · Two-way finite state automaton non-emptiness · One-way finite state automaton equivalence · Non-erasing stack automaton acceptance and nonemptiness [2] · Regular expression star freeness [3] · Quasi-realtime automaton acceptance? · Finite state automata intersection[4] [5] [6] · A generalized version of Langton's Ant[7] · Minimizing nondeterministic finite automata[8]

[edit] Formal languages

Context-sensitive language membership · Regular language intersection[9] [10] [11]

[edit] Networking

  • Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferences[12]

[edit] See also

[edit] References

  1. ^ Philipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete
  2. ^ Hopcroft, Motwani, and Ullman: Introduction to Automata Theory, Languages, and Computation (first or second edition)
  3. ^ Regular expression star-freeness is PSPACE-complete
  4. ^ D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
  5. ^ M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
  6. ^ 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.
  7. ^ Langton's Ant problem, "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)
  8. ^ http://www.cs.ucr.edu/~stelo/cpm/cpm05/cpm05_8_2_Ilie.pdf (Slide from University of California, Riverside lecture)
  9. ^ D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
  10. ^ M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
  11. ^ 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.
  12. ^ Alex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond. In SODA 2008.