Everything about PSPACE

🧭 Start here: a 6-step reading path

1. Read the overview: PSPACEA 5-minute orientation
2. Skim a recent paper: A continuous characterization of PSPACE using polynomial ordinary differential equationsInfluential work since 2022
3. Pick up a classic book: Algorithm designThe most-reprinted book on the subject
4. Read the landmark paper: IP = PSPACECited 431 times
5. Go sideways: Polynomial hierarchyA closely related topic
6. Go sideways: Complexity classA closely related topic

🏆 Landmark papers (most cited)

• IP = PSPACE

  Adi Shamir · 1992 · Journal of the ACM · 431 citations

• On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE- Hardness of the "Warehouseman's Problem"

  J.E. Hopcroft, J.T. Schwartz, M. Sharir · 1984 · The International Journal of Robotics Research · 282 citations

• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

  Harry B Hunt, Madhav V Marathe, Venkatesh Radhakrishnan · 1998 · Journal of Algorithms · 229 citations

• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

  Robert A. Hearn, Erik D. Demaine · 2005 · Theoretical Computer Science · 201 citations

• Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances

  Paul Bonsma, Luis Cereceda · 2009 · Theoretical Computer Science · 139 citations

• Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues

  Karl A. Abrahamson, Rodney G. Downey, Michael R. Fellows · 1995 · Annals of Pure and Applied Logic · 108 citations

• Satisfiability of word equations with constants is in PSPACE

  Wojciech Plandowski · 2004 · Journal of the ACM · 86 citations

• Hex ist PSPACE-vollst�ndig

  Stefan Reisch · 1981 · Acta Informatica · 73 citations

🆕 Influential since 2022

• A continuous characterization of PSPACE using polynomial ordinary differential equations

  Olivier Bournez, Riccardo Gozzi, Daniel S. Graça · 2023 · Journal of Complexity · 10 citations

• 6-Uniform Maker-Breaker Game is PSPACE-Complete

  Md Lutfar Rahman, Thomas Watson · 2023 · Combinatorica · 7 citations

• PSPACE-hardness of variants of the graph coloring game

  Carlos V.G.C. Lima, Thiago Marcilon, Nicolas Martins · 2022 · Theoretical Computer Science · 6 citations

• An Automaton Group with PSPACE-Complete Word Problem

  Jan Philipp Wächter, Armin Weiß · 2022 · Theory of Computing Systems · 6 citations

• Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems

  Laurent Bartholdi, Michael Figelius, Markus Lohrey · 2022 · ACM Transactions on Computation Theory · 5 citations

📚 Books worth reading

• Algorithm designJon Kleinberg, Éva Tardos · 1922
• Introduction to the theory of computationMichael Sipser · 1996
• 📕P*-spaces and strong P*-spacesReginald Dean Laursen · 1971
• 📕PSPACE-CompleteGerardus Blokdyk · 2018
• 📕PSPACE-CompleteGerard Blokdyk · 2017
• 📕On p-spaces and sub-paracompact spacesDennis Keith Burke · 1969
• 📕Espace Livre de Coloriage Pour les Enfantspspace plance · 2021
• 📕Space Coloring Book for Kids Ages 8-12pspace plance · 2021

Ranked by number of editions on Open Library, a rough measure of how lasting a book is.

🔗 Related topics

• Polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that…
• Complexity class In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly…
• EXPTIME In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable…
• NL (complexity) Unsolved problem in computer science ⁠𝖫=?𝖭𝖫⁠ More unsolved problems in computer science In computational complexity theory, NL (Nondeterministic Logarithmic-spa…
• P (complexity) In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can…
• PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input…
• Computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource…
• Space complexity The space complexity of an algorithm or a data structure is the amount of memory space required to solve an instance of the computational problem as a…