List of PSPACE-complete problems

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.

Games and puzzles

Generalized versions of:
Amazons· Atomix· Geography· Gomoku· Hex· Reversi· Rush Hour· Finding optimal play in Mahjong solitaire· Sokoban· Pebble game [Philipp Hertel and Toniann Pitassi: [http://www.cs.toronto.edu/~philipp/pages/papers/BWPebbling.pdf Black-White Pebbling is PSPACE-Complete] ]
* Ladder capturing in Go

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

Lambda calculus

Type inhabitation problem

Automata and language theory

Circuit theory

Integer circuit evaluation

Automata theory

Word problem for linear bounded automata· Two-way finite state automaton non-emptinessFact|date=October 2008· Equivalence problem for nondeterministic finite automata [ L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. InProceedings of the 5th Symposium on Theory of Computing, pages 1–9, 1973.] · Word problem and emptiness problem for non-erasing stack automata [ J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, second edition, 1979.] · Regular expression star freeness [ [http://www.inf.u-szeged.hu/actacybernetica/vol13n1/cikk1.xml Regular expression star-freeness is PSPACE-complete] ] · Quasi-realtime automaton acceptance?· Deterministic finite automata intersection emptiness [D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.] · A generalized version of Langton's Ant [ [http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php 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)] · Minimizing nondeterministic finite automata [T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal onComputing, 22(6):1117–1141, December 1993.]

Formal languages

Context-sensitive language membership· Regular language intersection [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.]

Networking

* Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferences [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] . In SODA 2008.]

See also

* List of NP-complete problems

References

* Wagner, K and Wechsung, G. Computational Complexity. D Reidel Publishing Company, 1986. ISBN 90-277-2146-7
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Eppstein's page on computational complexity of games]
* [http://arxiv.org/abs/cs.CC/0205005 Nondeterministic Constraint Logic]
* [http://arxiv.org/abs/cs.CC/9409225 The Complexity of Approximating PSPACE-complete problems]
* [http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6911/18589/00856751.pdf Integer circuit evaluation]
* [http://homepages.cwi.nl/~tromp/lad.ps Go ladders are PSPACE-complete]