Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 59 ยท Complexity

Space Complexity, PSPACE and Savitch's Theorem

Learn how memory is measured on a Turing machine, the classes L, NL and PSPACE, Savitch's theorem and TQBF, with Python demos of recursive reachability and QBF.

Time is not the only resource. A computation also needs memory, and memory behaves very differently from time: it can be reused. A program may run for an astronomically long time while only ever holding a handful of cells in use. That single difference makes space classes bigger and better behaved than time classes, and it makes nondeterminism almost free.

This lesson defines space complexity on a Turing machine, introduces the classes L, NL and PSPACE, proves (in outline) the surprising theorem of Savitch, and shows the canonical hard problem for PSPACE, quantified boolean formulas.

Measuring space

To make the measure meaningful even for tiny memory bounds, we use a two-tape model: a read-only input tape (the input is not counted) and a read-write work tape. The space used by a machine on input w is the number of work-tape cells it ever visits. The space complexity s(n) is the maximum over all inputs of length n.

TEXT
SPACE(s(n))  = languages decided by a deterministic TM using O(s(n)) cells
NSPACE(s(n)) = the same for nondeterministic machines

The four classes you must know:

Class Definition Intuition
L SPACE(log n) a fixed number of pointers into the input
NL NSPACE(log n) guess a path, remember only the current node
PSPACE โ‹ƒ SPACE(n^k) polynomial memory, any amount of time
NPSPACE โ‹ƒ NSPACE(n^k) nondeterministic polynomial memory

Logarithmic space sounds absurdly small, but it is enough to hold a couple of indices into the input. Checking whether a string is a palindrome, whether two numbers are equal, or whether a graph is connected in a restricted way can be done in L.

How time and space relate

A machine that uses s(n) cells can only be in a bounded number of configurations: a state, a head position, and the contents of the cells. The number of configurations is 2^O(s(n)). If the machine halts, it cannot repeat a configuration, so it halts within that many steps. Therefore:

  • SPACE(s(n)) โІ TIME(2^O(s(n))): anything in polynomial space runs in at most exponential time.
  • TIME(t(n)) โІ SPACE(t(n)): a machine cannot touch more cells than it takes steps.

Combining the two with what we know about NP gives the chain:

flowchart LR
    L["L"] --> NL["NL"]
    NL --> P["P"]
    P --> NP["NP"]
    NP --> PS["PSPACE"]
    PS --> EXP["EXPTIME"]

Every arrow is "is contained in". We know L โ‰  PSPACE and P โ‰  EXPTIME, so at least one arrow in between must be strict, but no individual inclusion is proved strict.

Why NP โІ PSPACE? Run through all certificates one after another, reusing the same work space for each: an exponential amount of time, but only polynomial space. The reuse of space is exactly what time cannot do.

Savitch's theorem

Nondeterminism seems to be a huge advantage for time (P versus NP is still open). For space, the gap is small.

Savitch's theorem. For every function s(n) โ‰ฅ log n, NSPACE(s(n)) โІ SPACE(s(n)^2). Consequently PSPACE = NPSPACE.

The proof simulates the nondeterministic machine on input w by answering a reachability question on its configuration graph: can the start configuration reach an accepting configuration? A deterministic procedure solves "can configuration u reach v in at most 2^t steps?" recursively:

TEXT
CANREACH(u, v, t):
    if t = 0: return u = v or u steps to v directly
    for each configuration m:
        if CANREACH(u, m, t-1) and CANREACH(m, v, t-1): return true
    return false

The recursion depth is t, which is about log2(number of configurations) = O(s(n)). Each level stores three configurations of size O(s(n)), so total space is O(s(n)^2). The cost is time, since the recursion tries every midpoint, but space is all we care about here.

Python Savitch's recursion for graph reachability

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The recursion goes only log2(n) levels deep, so memory stays tiny, but the number of calls explodes. This is the classic time-for-space trade: a quadratic space bound at the price of a lot of repeated work. Applied to the configuration graph, it shows that nondeterministic space can be simulated deterministically with only a squaring of memory.

Complement and NL

Another surprise comes from Immerman and Szelepcsenyi (1987): NL = coNL, and more generally NSPACE(s(n)) is closed under complement for s(n) โ‰ฅ log n. Compare this with time, where we do not know whether NP = coNP. Space classes are more symmetric because a machine can count: to certify that a node is not reachable, it can count how many nodes are reachable and verify that count, using only logarithmic extra memory.

The standard complete problem for NL is PATH: is there a path from s to t in a directed graph? Every NL problem reduces to PATH with a log-space reduction.

PSPACE and quantified boolean formulas

The NP-complete problem SAT asks whether a formula has some satisfying assignment (an existential question). A quantified boolean formula (QBF) allows both quantifiers:

TEXT
โˆƒx1 โˆ€x2 โˆƒx3 : (x1 โˆจ x2) โˆง (ยฌx2 โˆจ x3)

TQBF asks whether a fully quantified formula is true. It is the canonical PSPACE-complete problem: it is in PSPACE (by the recursion below), and every language in PSPACE reduces to it. You can read a QBF as a two-player game: an existential player picks values for the โˆƒ variables, a universal player picks the โˆ€ variables, and the formula is true when the first player has a winning strategy. That is why PSPACE-complete problems include generalized games such as generalized geography, Hex and Go-like puzzles on large boards.

The algorithm uses polynomial space because the recursion is only as deep as the number of variables, and each level stores one value:

Python Evaluating a QBF with depth-first recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n variables there are up to 2^n leaves, so the running time can be exponential, but the stack never holds more than n+1 frames of constant size each. That is polynomial space.

Quick summary of the landscape

Relationship Status
L โІ NL โІ P โІ NP โІ PSPACE โІ EXPTIME proved
PSPACE = NPSPACE proved (Savitch)
NL = coNL proved (Immerman-Szelepcsenyi)
L vs NL, P vs NP, NP vs PSPACE open
L โ‰  PSPACE and P โ‰  EXPTIME proved by hierarchy theorems

When you meet a new problem that involves alternating choices ("for every move of the opponent there exists a reply"), suspect PSPACE. When it involves a single "exists a solution" check, suspect NP.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is PSPACE = NPSPACE?

    Squaring a polynomial leaves it a polynomial, so Savitch's theorem makes deterministic and nondeterministic polynomial space equal.
  2. 2. Why does NP fit inside PSPACE?

    Enumerating certificates takes exponential time but only polynomial space, since the work area is cleared and reused for each certificate.
  3. 3. A machine that uses s(n) work cells and halts can run for at most about

    It can be in at most 2^O(s(n)) configurations, and a halting machine never repeats one.
  4. 4. TQBF is complete for which class?

    True quantified boolean formulas is the canonical PSPACE-complete problem; it generalizes SAT with alternating quantifiers.
  5. 5. Which result shows that space classes are closed under complement?

    Immerman and Szelepcsenyi showed NSPACE(s(n)) = coNSPACE(s(n)) for s(n) at least log n, in particular NL = coNL.

Summary

  • Space is measured as work-tape cells; unlike time it can be reused.
  • L is log space, NL is nondeterministic log space, PSPACE is polynomial space.
  • L โІ NL โІ P โІ NP โІ PSPACE โІ EXPTIME, and a halting machine with s(n) space runs in at most 2^O(s(n)) time.
  • Savitch's theorem gives PSPACE = NPSPACE by recursive midpoint search.
  • NL = coNL (Immerman-Szelepcsenyi); TQBF is PSPACE-complete and models two-player games.

Next: The Complexity Hierarchy and the P versus NP Question