Live briefing
Everything about PSPACE-complete
Type of decision problem in computer science
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 length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: PSPACE-completeA 5-minute orientation
- Skim a recent paper: 6-Uniform Maker-Breaker Game is PSPACE-CompleteInfluential work since 2022
- Pick up a classic book: Introduction to the theory of computationThe most-reprinted book on the subject
- Read the landmark paper: Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”Cited 60 times
- Go sideways: True quantified Boolean formulaA closely related topic
- Go sideways: Cook–Levin theoremA closely related topic
🏆 Landmark papers (most cited)
Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”
Finite-automaton aperiodicity is PSPACE-complete
The existential theory of equations with rational constraints in free groups is PSPACE-complete
The Othello game on an n × n board is PSPACE-complete
PSPACE-complete problems for subgroups of free groups and inverse finite automata
Solution to PSPACE‐Complete Problem Using P Systems with Active Membranes with Time‐Freeness
Reachability in two-clock timed automata is PSPACE-complete
Bounded-width QBF is PSPACE-complete
🆕 Influential since 2022
📚 Books worth reading
Introduction to the theory of computationMichael Sipser · 1996- 📕PSPACE-CompleteGerardus Blokdyk · 2018
- 📕PSPACE-CompleteGerard Blokdyk · 2017
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- True quantified Boolean formula In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean…
- Cook–Levin theorem In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete…
- EXPTIME In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable…
- Complexity class In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly…
- PSPACE Unsolved problem in computer science 𝖯=?𝖯𝖲𝖯𝖠𝖢𝖤 More unsolved problems in computer science In computational complexity theory, PSPACE is the set…
- NP-hardness In computational complexity theory, a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time…
- Computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource…
- Alternating Turing machine In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations…