P33 · Space vs Time

🔊 Listen

1 · The space–time sandwich

Time and space measure two different resources of a Turing machine: how many steps it takes vs how many distinct tape cells it uses. The two are related but not identical, captured by Sipser's fundamental sandwich theorem.

Inclusion theorem (Sipser §8.1)

For any space-constructible function f(n) ≥ log n:

TIME(f(n)) ⊆ SPACE(f(n)) ⊆ TIME(2^O(f(n)))

Both inclusions have one-line proofs:

TIME ⊆ SPACE: in t(n) steps a TM can visit at most t(n) distinct cells. So a t(n)-time machine uses ≤ t(n) space.
SPACE ⊆ TIME(exp): a TM using s(n) cells has at most |Q| · s(n) · |Γ|^s(n) = 2^O(s(n)) distinct configurations. If it ever revisits one, it loops — so a halting space-bounded machine runs for at most 2^O(s(n)) steps.

Consequences for classes

P ⊆ PSPACE ⊆ EXPTIME. Each containment is via the sandwich theorem at a specific scale.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

f(n) ≥ log n is a real requirement. Sublogarithmic space is too small to even index the input position — most theorems break below log n.
"Space" excludes the input tape. Standard convention (Sipser): space = work-tape cells used. The input tape is read-only and doesn't count. Otherwise PSPACE would equal P trivially via input length.
The exponential gap is real and visible. NL ⊆ P via Savitch; PSPACE ⊆ EXPTIME via the configuration bound. Both gaps are known to be at least as large as polynomial — and either could be equality (open).

🔊 Listen

4 · Q&A defence notes

Q1. Why isn't TIME = SPACE?
Space can be reused; time can't. A SPACE(f)-bounded machine can revisit the same cells exponentially many times before either halting or entering a loop. Time can't be reused — once a step is taken, it's gone.
Q2. Real examples of "space-cheap, time-expensive"?
Depth-first search with explicit stack: O(depth) space, but exponentially many leaves to explore in worst case. Branch-and-bound, alpha-beta pruning, recursive backtracking — all use polynomial space with exponential running time.
Q3. Is the SPACE ⊆ TIME(exp) bound tight?
In the relativised world, yes — there are oracles separating PSPACE from EXPTIME. Whether PSPACE = EXPTIME or PSPACE ⊊ EXPTIME is open.
Q4. Where does NL fit?
NL = NSPACE(log n). NL ⊆ P (Savitch's theorem plus deterministic simulation). NL ⊆ PSPACE trivially. NL = coNL (Immerman–Szelepcsényi).

🔊 Listen

5 · Where to read more

Sipser: §8.1 (space complexity). Lecture notes: Module 6 slide 1. Companion problems: P34 (Savitch tree), P35 (PSPACE vs NPSPACE), P63 (NP ⊆ EXPTIME).