Preply — Study more efficiently by working with a personal tutor. Get 50% off.Affiliate

Wikipedia

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:

Logic

Lambda calculus Type inhabitation problem for simply typed lambda calculus

Automata and language theory

Circuit theory Integer circuit evaluation

Automata theory

Formal languages

Graph theory

Others

See also List of NP-complete problems

Notes

References Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. Eppstein's page on computational complexity of games The Complexity of Approximating PSPACE-complete problems for hierarchical specifications

Tags

  • Lists of problems
  • Mathematics-related lists
  • PSPACE-complete problems