Complexity — DTIME, DSPACE, complexity classes: Visual walkthrough

This is the visual companion to the parent note. Read that for the definitions; read this to see why they connect.

Step 0 — The one object everything is measured against

Before any inclusion, we must agree on what we are counting. Everything below lives inside one picture: a Turing machine's tape.

Figure — Complexity — DTIME, DSPACE, complexity classes

The one fact that drives the entire page is written in orange on the figure: in a single step the head cannot jump. It shuffles by one cell, or stays put. Hold onto that — it is the seed of Step 1.

Recall

What is the maximum distance the head can move in a single step? ::: One cell (left or right), or it stays put.

Step 1 — Time bounds Space: $DTIME (f) \subseteq DSPACE (f)$

WHAT. We show: if a machine finishes in $f (n)$ steps, it never touches more than about $f (n)$ cells. In symbols, being fast forces being thrifty with memory.

WHY. From Step 0, one step = one cell of movement at most. So the set of cells the head can possibly reach grows by at most one on each side per step. It is a spreading stain, not a teleport.

PICTURE. Look at the figure: the head starts at one cell (step 0), and the shaded "visited" region widens by at most one cell per tick. After $f (n)$ ticks the whole stain is at most $f (n) + 1$ cells wide.

Dropping constants (the $+ 1$ ) via big-O, space $\leq O (f)$ . So every language in $DTIME (f)$ is also in $DSPACE (f)$ .

Step 2 — A "snapshot" of the whole machine: the configuration

To go the other direction (space bounding time) we need a new idea. We cannot count cells anymore; we must count entire situations the machine can be in.

WHAT. We define a configuration = a complete photograph of the machine at one instant.

WHY. If we know every possible photograph, and we know a halting machine can never repeat a photograph, then the number of photographs caps the number of steps. This is the whole trick of Step 3 — but first we must count photographs.

PICTURE. The figure shows one configuration as three ingredients glued together: the current state (mood), where the head sits, and the contents of the used cells.

Step 3 — Counting configurations: Space bounds Time

WHAT. We show $DSPACE (f) \subseteq DTIME (2^{O (f)})$ for $f \geq lo g n$ : a machine using $f (n)$ cells must halt within $2^{O (f (n))}$ steps.

WHY. A machine that halts can never revisit a configuration — if it did, it would do the exact same thing forever and loop, never halting. So the number of distinct configurations is a hard ceiling on the number of steps. Now we just multiply the choices for each ingredient from Step 2.

PICTURE. The figure lays the three ingredients side by side as a multiplication: a modest number of states, times $f (n)$ head positions, times a tower of tape possibilities.

Because a halting machine runs at most $# configs$ steps, its running time is $\leq 2^{O (f (n))}$ . Bounded space forces bounded time. This is the arrow $PSPACE \subseteq EXP$ .

Step 4 — The configuration graph, and why $NL \subseteq P$

WHAT. Turn the configurations into a graph: draw an arrow from config $C$ to config $C^{'}$ if one step of the machine takes $C$ to $C^{'}$ . Deciding whether the machine accepts becomes: "is there a path from the start config to an accepting config?"

WHY. For a log-space machine ( $f = lo g n$ ), Step 3 gives $2^{O (l o g n)} = n^{O (1)}$ configurations — only polynomially many nodes. Searching a polynomial graph for a path (breadth-first search) is a polynomial-time job. That single observation is exactly $NL \subseteq P$ , and its deterministic sibling $L \subseteq P$ .

PICTURE. The figure draws the config graph: start node in teal, accepting node in orange, and a highlighted path of arrows the search would trace.

This is also why Reachability (does a directed graph have an $s \to t$ path?) is the beating heart of $NL$ : a nondeterministic machine just guesses the next node, storing only the current node — an $O (lo g n)$ -bit name. See NP-Completeness and Reductions for how "complete" problems like this pin down a whole class.

Step 5 — The cheap inclusions: $L \subseteq NL$ and $NP \subseteq PSPACE$

WHAT. Two easy links close the chain.

WHY / PICTURE. The figure splits into two panels:

Left (D $\subseteq$ N): every deterministic machine is a nondeterministic one that simply never bothers to guess. So $L \subseteq NL$ and $P \subseteq NP$ for free.
Right (guess-and-reuse): an $NP$ problem has a short certificate (a candidate answer of polynomial length). A $PSPACE$ machine can try every certificate one after another, reusing the same tape each time — so total space stays polynomial even though there are exponentially many certificates. Hence $NP \subseteq PSPACE$ .

Step 6 — The degenerate cases we must not skip

A derivation isn't finished until every corner is checked.

Step 7 — Savitch cheaply, and why some inclusions are strict

WHAT. Two capstones: nondeterministic space is not much stronger than deterministic space (Savitch's Theorem), and some links in the chain are provably strict (Hierarchy Theorems).

WHY (Savitch). To ask "can config $A$ reach config $B$ in $\leq 2^{k}$ steps?", pick a midpoint config $M$ : $A$ reaches $B$ iff for some $M$ , $A$ reaches $M$ in $\leq 2^{k - 1}$ steps and $M$ reaches $B$ in $\leq 2^{k - 1}$ steps. Each halving is one level of recursion; there are only $k = O (f)$ levels, and each level stores one config of size $O (f)$ . Reusing space down the recursion: $NSPACE (f) \subseteq DSPACE (f^{2}) .$ The $f^{2}$ is (depth $O (f)$ ) $\times$ (space $O (f)$ per level). Corollary: $NPSPACE = PSPACE$ .

WHY (strictness). With genuinely more time you can simulate every smaller-time machine and then flip its answer on its own description — a diagonalization. The flipped language provably escapes the smaller class. That is why $P ⊊ EXP$ is known, while $P$ vs $NP$ (same resource, only D-vs-N) stays open.

The one-picture summary

Everything above compresses into a single ladder: each rung is a class, each arrow an inclusion we derived, colour-coded by which step earned it.

Recall Feynman retelling — say the whole walkthrough in plain words

A Turing machine's head can only shuffle one cell per tick, so it can't touch more cells than it takes steps — that's time-bounds-space (Step 1). Going the other way, freeze the machine into a photograph called a configuration; a machine that stops can never take the same photograph twice, so the number of possible photographs caps the number of steps — and counting photographs (states × head-spots × tape-fillings) gives about $2^{f}$ , so space-bounds-exponential-time (Step 3). Shrink space to $lo g n$ and there are only polynomially many photographs, so you can just search that photograph-graph in polynomial time — that's $NL \subseteq P$ (Step 4). Determinism is a lazy nondeterminism, and you can reuse memory to try every guess one at a time, which glues $NP$ inside $PSPACE$ (Step 5). We double-check the corners: non-halting machines are someone else's problem, and you need at least $lo g n$ space just to point at the input (Step 6). Finally, Savitch says nondeterministic space costs only its square to determinize, and diagonalization proves that more time truly buys more languages, which is why $P \neq = EXP$ is settled but $P$ vs $NP$ is not (Step 7). Stack it all up and you get the ladder $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP$ .