Time and Space as Resources

Asymptotic notation gave us a language for how one algorithm's cost grows. Complexity theory asks a bigger, coarser question: forget the individual algorithm — what can be computed at all within a given budget of time, or of memory? Group every problem solvable within some budget into a bucket, and you get a complexity class. The landscape of these buckets — which sits inside which, which are provably different, which nobody can tell apart — is the map on which the whole subject is drawn.

To make "a budget of time or memory" precise we need a machine simple enough to count steps on honestly. That machine is the Turing machine, and the two resources we meter are the number of steps it takes (time) and the number of tape cells it touches (space).

Measuring time and space on a Turing machine

Fix a Turing machine M and an input w of length n = |w|. Two counters tell us the cost:

Time t_M(w) — the number of transition steps M executes before halting on w.
Space s_M(w) — the number of distinct tape cells M ever visits (scans) during that run.

We report both as functions of the input length, taking the worst case over all inputs of that length: t_M(n) = \max_{|w| = n} t_M(w), and likewise for space. A machine runs in time f(n) if t_M(n) \le f(n) for all n, and in space f(n) if s_M(n) \le f(n).

One subtlety makes space the more delicate resource. For sublinear space — memory smaller than the input itself, like O(\log n) — we cannot count the input tape, since just holding the input already costs n cells. The fix is a read-only input tape (which doesn't count) plus a separate read/write work tape (which does). Space is then measured on the work tape alone, and asking for O(\log n) memory becomes meaningful: enough to store a constant number of pointers into the input, not the input.

Both directions have a clean bound. Space is cheaper than time because each step visits at most one new cell, so s_M(n) \le t_M(n) + O(1) — you can't touch more memory than you have steps to touch it with. The reverse is looser: a machine using space s \ge \log n has at most 2^{O(s)} distinct configurations (tape contents × head positions × state), and a halting machine never repeats a configuration, so t_M(n) \le 2^{O(s_M(n))}. Small space forces at-most-exponential time; small time forces at-most-linear space. These two inequalities are the hinges that hold the whole class hierarchy together.

From a machine to a class: DTIME, DSPACE, and their nondeterministic twins

A complexity class collects languages (decision problems — sets of strings we want to recognise), not machines. We say a language L lives in a time class if some machine decides it within the budget:

\mathrm{DTIME}(f(n)) — languages decided by a deterministic TM in time O(f(n)).
\mathrm{DSPACE}(f(n)) — languages decided by a deterministic TM in space O(f(n)).
\mathrm{NTIME}(f(n)) — languages decided by a nondeterministic TM in time O(f(n)) (it accepts iff some computation branch accepts within the budget).
\mathrm{NSPACE}(f(n)) — the nondeterministic space analogue.

The single most important shift in mindset here: a complexity class is a set of languages — a set of problems — not a set of algorithms and not a property of one program. "L \in \mathrm{DTIME}(n^2)" is a claim that the problem L can be solved in quadratic time by some machine, however cleverly. Two classes are equal when they contain exactly the same problems; one contains another when every problem in the smaller is also in the larger.

The named classes: P, NP, L, PSPACE, EXP

Individual budgets like \mathrm{DTIME}(n^2) are brittle — bump the exponent and you get a different class. The famous classes are unions over a whole family of budgets, which makes them robust to the small model choices (tape count, alphabet size) that only ever change running time by a polynomial factor.

\mathrm{P} = \bigcup_{k \ge 1} \mathrm{DTIME}(n^k) — decidable in polynomial time. The class we identify with "efficiently solvable".
\mathrm{NP} = \bigcup_{k \ge 1} \mathrm{NTIME}(n^k) — nondeterministic polynomial time; equivalently, solutions verifiable in polynomial time given a short certificate.
\mathrm{L} = \mathrm{DSPACE}(\log n) — logarithmic space: a handful of pointers into a read-only input.
\mathrm{PSPACE} = \bigcup_{k \ge 1} \mathrm{DSPACE}(n^k) — polynomial space (time unlimited).
\mathrm{EXP} = \bigcup_{k \ge 1} \mathrm{DTIME}(2^{n^k}) — exponential time.

Notice how each definition picks one resource and one growth family. P and NP cap time at a polynomial; L and PSPACE cap space; EXP loosens time all the way to exponential. The polynomial ones are unions precisely so that "which polynomial" never matters — a detail we will lean on hard when we argue that P is the same class no matter which reasonable machine model you pick.

How the classes nest

These five classes fall into one long chain of inclusions. Each containment has a one-line reason, built from the time/space trade-offs above.

\mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXP}

\mathrm{L} \subseteq \mathrm{P}: a machine using O(\log n) space has only 2^{O(\log n)} = n^{O(1)} configurations, so if it halts it halts in polynomial time.
\mathrm{P} \subseteq \mathrm{NP}: determinism is a special case of nondeterminism (one branch is still "some branch").
\mathrm{NP} \subseteq \mathrm{PSPACE}: try each polynomial-length certificate in turn, reusing the same polynomial chunk of space for each — lots of time, little memory.
\mathrm{PSPACE} \subseteq \mathrm{EXP}: polynomial space allows only 2^{n^{O(1)}} configurations, so a halting run finishes in exponential time.

We know the two ends differ. The time hierarchy theorem proves \mathrm{P} \subsetneq \mathrm{EXP}: strictly more time genuinely buys strictly more computing power, so \mathrm{P} \ne \mathrm{EXP}. Likewise the space hierarchy theorem gives \mathrm{L} \subsetneq \mathrm{PSPACE}. Since the whole chain runs from L to EXP and its endpoints are provably different, at least one of the four inclusions in between must be strict — we simply cannot yet say which. That single "somewhere here is a real gap, but we can't point at it" is the emotional core of the entire field.

Which inclusions are known to be strict?

Here is the honest scorecard — and it is a humbling one. Of the four links in the chain, exactly zero are individually proven strict, yet two non-adjacent separations are known.

Relation	Status	Why
\mathrm{L} \subsetneq \mathrm{PSPACE}	Known strict	Space hierarchy theorem
\mathrm{P} \subsetneq \mathrm{EXP}	Known strict	Time hierarchy theorem
\mathrm{L} \subseteq \mathrm{P}	Open	Nobody knows if they are equal
\mathrm{P} \subseteq \mathrm{NP}	Open	The famous P vs NP question
\mathrm{NP} \subseteq \mathrm{PSPACE}	Open	Nobody knows if they are equal

The two hierarchy separations act like distant fence-posts: they force a strict gap somewhere along \mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} without revealing its location. Proving any single one of those four middle links strict — most famously \mathrm{P} \ne \mathrm{NP} — would be a landmark result and, in that one case, a million-dollar one.

Students often collapse two very different statements: "we cannot prove \mathrm{P} \ne \mathrm{NP}" and "P and NP might well be equal". The first is a fact about the current state of mathematics; the second is a conjecture almost every expert rejects. The consensus belief is that \mathrm{L}, \mathrm{P}, \mathrm{NP}, \mathrm{PSPACE} are all distinct and every inclusion in the chain is strict — we just have no proof. So never write "\mathrm{P} = \mathrm{NP} is unknown, therefore they're probably the same." Unknown means unproven, not undecided-by-the-evidence. And beware the reverse slip too: the arrows are inclusions, so \mathrm{P} \subseteq \mathrm{NP} is a theorem — it's only the strictness that's open.