Time & Space Hierarchy Theorems

Diagonalization: more time and space buy strictly more power.

The idea

The hierarchy theorems state that a Turing machine given asymptotically more time, or more space, decides strictly more languages.

Theorem (Time hierarchy theorem).

If $f$ is time-constructible and $g(n) = o\!\left(\dfrac{f(n)}{\log f(n)}\right)$, then $\mathsf{TIME}(g) \subsetneq \mathsf{TIME}(f)$.

Theorem (Space hierarchy theorem).

If $f$ is space-constructible and $g(n) = o(f(n))$, then $\mathsf{SPACE}(g) \subsetneq \mathsf{SPACE}(f)$.

These separations are unconditional, and complexity theory has few of those: whether $\mathsf{P} = \mathsf{NP}$ is open, but $\mathsf{P} \subsetneq \mathsf{EXP}$ follows from the time theorem.

The side conditions carry real content. A function is constructible when a machine can compute the budget $f(n)$ within that same budget, so that a computation can be cut off when its allowance runs out. And the gap between $g$ and $f$ is not the same in the two theorems: the time theorem asks for a logarithmic factor of room that the space theorem does without, so the space theorem is the tighter of the two.

Ways to work on it

• Walkthrough. Diagonalization, the time theorem's gap, and the tighter space theorem.
• Practice. Decide whether a hierarchy theorem separates a given pair of bounds.
• Hardest. Derive P EXP from the time hierarchy theorem.

Not sure where to start? Take the ten-question placement test.