Space Complexity and PSPACE

While time complexity often dominates discussions of computational efficiency, understanding space complexity is equally crucial for characterizing problems where memory, not time, is the primary constrained resource. This field reveals fundamental hierarchies about problem solvability within limited memory, from logarithmic to polynomial bounds, and challenges intuitions about the power of nondeterminism. Grasping these concepts is essential for advanced algorithm design and for mapping the landscape of computational difficulty.

Foundations of Space Complexity Classes

Space complexity measures the maximum amount of memory or workspace a Turing machine uses during computation, as a function of input size. We typically focus on asymptotic complexity, ignoring constant factors. The most fundamental classes are defined by their space bounds. The class L (or LOGSPACE) contains decision problems solvable by a deterministic Turing machine using $O(\log n)$ workspace, where $n$ is the input length. This represents problems solvable with only a logarithmic number of bits beyond the input, such as checking connectivity in an undirected graph. The class NL (Nondeterministic Logarithmic space) consists of problems solvable by a nondeterministic Turing machine within $O(\log n)$ space. A canonical NL-complete problem is deciding whether there is a directed path from a start to an end node in a directed graph.

A more expansive class is PSPACE, which includes all problems solvable by a deterministic Turing machine using polynomial space, i.e., $O(n^k)$ for some constant $k$. Crucially, PSPACE encompasses all problems in NP and co-NP, because a polynomial-space machine can simulate all possible branches of a nondeterministic polynomial-time computation by reusing space. The known relationships are $L\subseteq NL\subseteq P\subseteq NP\subseteq PSPACE$. A major open question is whether any of these inclusions, particularly $L$ vs. $NL$ or $P$ vs. $PSPACE$, are strict.

Savitch's Theorem: Relating Deterministic and Nondeterministic Space

A cornerstone result is Savitch's theorem, which states that for any space-constructible function $f(n)\ge \log n$, we have $NSPACE(f(n))\subseteq SPACE(f(n{)}^2)$. In practical terms, this means that nondeterministic space classes are not vastly more powerful than deterministic ones when it comes to space efficiency; they differ by at most a polynomial factor. The theorem implies $NL\subseteq SPACE({\log }^{2}n)$, and more broadly, $PSPACE=NPSPACE$.

The proof is constructive and uses a clever recursive algorithm for reachability. To decide if there is a path from node $u$ to $v$ within $2^k$ steps using limited space, the algorithm guesses an intermediate node $z$ and recursively checks paths from $u$ to $z$ and $z$ to $v$. Because the recursion depth is logarithmic in the number of steps, and each level uses $O(\log n)$ space to store node identifiers, the total space is $O({\log }^{2}n)$. This demonstrates how space can be reused aggressively, trading exponential time for polynomial space in the simulation.

PSPACE-Completeness: The Hardest Problems in Polynomial Space

To understand the limits of PSPACE, we study PSPACE-complete problems. A problem is PSPACE-complete if it is in PSPACE and every other problem in PSPACE is polynomial-time reducible to it. These are the most difficult problems within PSPACE, analogous to NP-complete problems for NP. The quintessential PSPACE-complete problem is the quantified Boolean formula (QBF) problem. Given a Boolean formula with variables quantified by existential ($\exists$) and universal ($\forall$) quantifiers, such as $\forall x\exists y(x\vee y)$, the problem asks if the formula is true. Evaluating such formulas requires checking all assignments, which can be done in polynomial space by recursively trying possibilities, but appears to require exponential time.

Another rich source of PSPACE-complete problems is generalized games like Geography or Generalized Chess played on an $n\times n$ board. In these games, players alternate moves, and the decision problem "does the first player have a winning strategy?" can be modeled as a QBF evaluation. The game tree has exponential size, but a polynomial-space algorithm can perform a depth-first search using backtracking, storing only the current path. This contrasts with NP-completeness, which often corresponds to "does there exist a single winning move?" for one player.

The Immerman-Szelepcsényi Theorem: NL is Closed Under Complement

A surprising and profound result is the Immerman-Szelepcsényi theorem, which states that NL is closed under complement. That is, if a problem is in NL, its complement (the "no" instances) is also in NL. Formally, $NL=coNL$. This was unexpected because the analogous question for time complexity—whether $NP=coNP$—remains famously open.

The theorem's proof involves a clever counting argument that avoids explicitly storing all reachable nodes, which would exceed logarithmic space. For the canonical NL-complete problem of graph non-reachability, the algorithm iteratively counts the number of nodes reachable from the start within a certain distance. By maintaining a counter that uses $O(\log n)$ bits and carefully verifying counts, it can determine that the target node is not among the reachable nodes. This result implies that for logarithmic space, nondeterminism does not provide asymmetry between "yes" and "no" answers, a property not known to hold for polynomial time.

Common Pitfalls

When studying space complexity, several conceptual errors frequently arise. First, do not conflate space complexity with time complexity. A problem solvable in polynomial time (P) is always in polynomial space (PSPACE), but the converse is not known to be true; a polynomial-space algorithm might take exponential time, as seen in Savitch's theorem's simulation.

Second, a common misunderstanding of Savitch's theorem is to think it implies $P=NP$. The theorem deals with space, not time. While $NL\subseteq SPACE({\log }^{2}n)$, the deterministic simulation might take exponential time, so it does not translate to a polynomial-time equivalence between deterministic and nondeterministic models.

Third, when encountering PSPACE-complete problems, avoid assuming they are harder than NP-complete problems in a practical sense. Both classes contain intractable problems, but PSPACE-completeness indicates that memory, not just time, is a critical barrier. For instance, QBF is PSPACE-complete, while SAT is NP-complete; both are hard, but for different theoretical reasons.

Finally, do not overgeneralize the Immerman-Szelepcsényi theorem. It applies specifically to logarithmic space and does not prove that $NP=coNP$. The techniques used rely heavily on the limited space bound and do not directly extend to polynomial time.

Summary

• Space complexity classes like L (log-space), NL (nondeterministic log-space), and PSPACE (polynomial space) categorize problems by memory requirements, with known inclusions $L\subseteq NL\subseteq P\subseteq NP\subseteq PSPACE$.
• Savitch's theorem shows that nondeterministic space is not vastly more powerful than deterministic space, as $NSPACE(f(n))\subseteq SPACE(f(n{)}^2)$, implying $NL\subseteq SPACE({\log }^{2}n)$ and $PSPACE=NPSPACE$.
• PSPACE-complete problems, such as evaluating quantified Boolean formulas (QBF) and deciding winners in generalized games, are the hardest problems solvable with polynomial space, often requiring exponential time.
• The Immerman-Szelepcsényi theorem proves $NL=coNL$, meaning nondeterministic logarithmic space is closed under complement, a property not known for higher complexity classes like NP.
• Understanding these concepts highlights that memory constraints define fundamental computational limits independently of time, with implications for algorithm design and complexity theory.