Why does the time hierarchy theorem separate two deterministic time classes when no explicit hard problem is known?

seniorshould knowfreq 44%

answer

the hard language is built, not found
simulate under a clock, then disagree
self-reference on a machine encoding
simulation overhead costs a log factor
the bound must be constructible

basics

~20 s

The theorem builds its own hard language by diagonalization: a machine that simulates every cheaper machine under a clock and returns the opposite verdict. That language needs the larger budget by construction, so no natural hard problem has to be exhibited.

solid answer

~50 s

The separation is constructive in a very literal sense: instead of finding a problem that needs more time, the proof manufactures one. Build a machine D that reads its input as the encoding of another machine M, simulates M on that same input under a clock set by the larger budget, and answers the opposite of whatever M answers. No machine inside the smaller budget can decide D's language, because on long enough encodings of that machine the clock never fires and D deliberately disagrees with it. D itself stays inside the larger budget because the clock enforces it. The gap has to be more than a constant factor: simulating another machine step by step costs a logarithmic factor in time, which is why the theorem requires g(n) log g(n) to be dominated by f(n). The space version needs only an asymptotic increase, because tracking another machine's tape costs a constant factor in space.

The separation is constructive in a very literal sense: instead of finding a problem that needs more time, the proof *manufactures* one. Build a machine `D` that reads its input as the encoding of another machine `M`, simulates `M` on that same input under a clock set by the larger budget, and answers the opposite of whatever `M` answers. No machine inside the smaller budget can decide `D`'s language, because on long enough encodings of that machine the clock never fires and `D` deliberately disagrees with it. `D` itself stays inside the larger budget because the clock enforces it. The gap has to be more than a constant factor: simulating another machine step by step costs a logarithmic factor in time, which is why the theorem requires `g(n) log g(n)` to be dominated by `f(n)`. The space version needs only an asymptotic increase, because tracking another machine's tape costs a constant factor in space.

code

pseudocode · 14 lines

pseudocode

function D(x):
    if x does not encode a machine:
        accept
    M = the machine encoded by x
    budget = f(length of x)          # counted in this machine's own steps
    while budget > 0:
        simulate one step of M running on input x
        budget = budget - cost of that simulated step
        if M has halted:
            if M accepted x:
                reject               # deliberately disagree
            else:
                accept               # deliberately disagree
    reject                           # budget exhausted: fixed default

go deeper

for a junior

Take away the headline: there is a theorem saying that strictly more time decides strictly more problems, and it is what makes exponential time provably stronger than polynomial time.

for a middle

Be able to sketch the construction - simulate the machine your input encodes, under a clock, then answer the opposite - and say why the constructed language cannot be decided cheaply.

for a senior

Explain the hypotheses that make it work: constructible bounds, a gap wider than the simulation overhead, and why the space version is tighter than the time version.

for a principal

Judge what such a result licenses in a plan. It separates one resource kind from itself at an exponential gap and manufactures an artificial witness; it tells you nothing about which of your workloads is hard.

What the theorem claims

The time hierarchy theorem says that more time buys strictly more: for a time-constructible bound f, if g(n) log g(n) grows strictly slower than f(n), some language is decidable in time f(n) and by no machine running in time g(n). The space hierarchy theorem says the same for work space, with a weaker hypothesis - any asymptotic increase in a space-constructible bound is enough. The famous corollary is the one clean separation in the deterministic chain: P is strictly inside EXPTIME.

The question an engineer actually asks is how anyone proves an impossibility without producing the hard problem. The answer is that the proof produces one, by construction rather than by discovery.

The construction: a machine built to disagree

Read the input as an encoding of a machine M, allowing trailing filler so that every machine is described by arbitrarily long inputs.
Simulate M on that very same input, step by step, charging each simulated step against a budget fixed by f(n).
If the budget runs out first, answer with a fixed default.
If M halts first, answer the opposite of what M answered.

Call the constructed machine D and its language Ld. Suppose some machine M decided Ld within time g. Because g(n) log g(n) is dominated by f(n), on all sufficiently long encodings of M the simulation finishes before the budget is gone - so D sees M's verdict and returns the opposite. Then D and M disagree on that input, contradicting the assumption that M decides Ld. Meanwhile D never exceeds its own budget, because the budget is enforced rather than hoped for, so Ld sits inside the larger time class.

The self-reference is the engine: the language is defined by disagreeing with everything cheaper, which is why nobody can point at it and say what it is about.

Why time loses a logarithmic factor and space does not

	time hierarchy	space hierarchy
gap required	`g log g` dominated by `f`	`g` dominated by `f`
source of the loss	step-by-step simulation overhead	none beyond a constant factor
hypothesis on the bound	time-constructible	space-constructible
flagship corollary	P strictly inside EXPTIME	L strictly inside PSPACE

A universal simulator has to decode the simulated machine's transition table and keep its tapes on a fixed number of its own, and the standard simulation pays a logarithmic factor in time for that bookkeeping.
Space is different: the simulator can hold the simulated tape contents essentially verbatim and spend only a constant factor more, so no logarithmic slack appears in the statement.

Constructibility, and what happens without it

A bound is time-constructible when the bound itself can be computed within roughly that budget. The clock has to be affordable, or the construction cannot enforce it.
Without that hypothesis the slogan is simply false. There are pathological pairs of bounds between which no new language appears at all, so "a bigger budget always buys something" is not a law of nature; it is a theorem with conditions.

Padding: lifting a result up the chain

Padding is the companion trick, and its direction is where candidates slip.

Rewrite each input as itself followed by a long block of filler, so that a machine reading the padded input has a budget that is polynomial in the padded length while being exponential in the original length.
Worked case: if L equalled P, then PSPACE would equal EXPTIME. Take a language decided in exponential time and pad each input to exponential length. The padded language is then decidable in polynomial time; if L equalled P it would be decidable in logarithmic space of the padded length, which is polynomial space measured against the original input - putting the original language in PSPACE. Since PSPACE already sits inside EXPTIME, they would coincide.
The direction: padding propagates a collapse upward, and therefore a separation downward. Proving PSPACE differs from EXPTIME would prove L differs from P. The reverse inference does not hold.

What the theorem does not give you

No natural problem. The separating language is a self-referential artefact nobody wants to solve. Knowing that some problem needs exponential time is a different thing from knowing which useful one does.
No help across resource kinds or machine modes. It compares deterministic time with deterministic time, which is exactly why it stops short of every open step in the chain.
No practical threshold. The statement is asymptotic; it says nothing about the input sizes a real system handles.

## What the theorem claims The **time hierarchy theorem** says that more time buys strictly more: for a time-constructible bound `f`, if `g(n) log g(n)` grows strictly slower than `f(n)`, some language is decidable in time `f(n)` and by no machine running in time `g(n)`. The **space hierarchy theorem** says the same for work space, with a weaker hypothesis - any asymptotic increase in a space-constructible bound is enough. The famous corollary is the one clean separation in the deterministic chain: **P is strictly inside EXPTIME**. The question an engineer actually asks is how anyone proves an impossibility without producing the hard problem. The answer is that the proof produces one, by construction rather than by discovery. ## The construction: a machine built to disagree 1. Read the input as an encoding of a machine `M`, allowing trailing filler so that **every** machine is described by arbitrarily long inputs. 2. Simulate `M` on that very same input, step by step, charging each simulated step against a budget fixed by `f(n)`. 3. If the budget runs out first, answer with a fixed default. 4. If `M` halts first, answer the **opposite** of what `M` answered. Call the constructed machine `D` and its language `Ld`. Suppose some machine `M` decided `Ld` within time `g`. Because `g(n) log g(n)` is dominated by `f(n)`, on all sufficiently long encodings of `M` the simulation finishes before the budget is gone - so `D` sees `M`'s verdict and returns the opposite. Then `D` and `M` disagree on that input, contradicting the assumption that `M` decides `Ld`. Meanwhile `D` never exceeds its own budget, because the budget is enforced rather than hoped for, so `Ld` sits inside the larger time class. The self-reference is the engine: the language is defined by disagreeing with everything cheaper, which is why nobody can point at it and say what it is *about*. ## Why time loses a logarithmic factor and space does not | | time hierarchy | space hierarchy | |---|---|---| | gap required | `g log g` dominated by `f` | `g` dominated by `f` | | source of the loss | step-by-step simulation overhead | none beyond a constant factor | | hypothesis on the bound | time-constructible | space-constructible | | flagship corollary | P strictly inside EXPTIME | L strictly inside PSPACE | - A universal simulator has to decode the simulated machine's transition table and keep its tapes on a fixed number of its own, and the standard simulation pays a logarithmic factor in **time** for that bookkeeping. - **Space** is different: the simulator can hold the simulated tape contents essentially verbatim and spend only a constant factor more, so no logarithmic slack appears in the statement. ## Constructibility, and what happens without it - A bound is **time-constructible** when the bound itself can be computed within roughly that budget. The clock has to be affordable, or the construction cannot enforce it. - Without that hypothesis the slogan is simply false. There are pathological pairs of bounds between which no new language appears at all, so "a bigger budget always buys something" is not a law of nature; it is a theorem with conditions. ## Padding: lifting a result up the chain Padding is the companion trick, and its direction is where candidates slip. - Rewrite each input as itself followed by a long block of filler, so that a machine reading the padded input has a budget that is polynomial in the **padded** length while being exponential in the original length. - Worked case: **if L equalled P, then PSPACE would equal EXPTIME.** Take a language decided in exponential time and pad each input to exponential length. The padded language is then decidable in polynomial time; if L equalled P it would be decidable in logarithmic space of the padded length, which is polynomial space measured against the original input - putting the original language in PSPACE. Since PSPACE already sits inside EXPTIME, they would coincide. - The direction: padding propagates a **collapse upward**, and therefore a **separation downward**. Proving PSPACE differs from EXPTIME would prove L differs from P. The reverse inference does not hold. ## What the theorem does not give you - **No natural problem.** The separating language is a self-referential artefact nobody wants to solve. Knowing that *some* problem needs exponential time is a different thing from knowing which useful one does. - **No help across resource kinds or machine modes.** It compares deterministic time with deterministic time, which is exactly why it stops short of every open step in the chain. - **No practical threshold.** The statement is asymptotic; it says nothing about the input sizes a real system handles.

The simulator answers a fixed default when its budget runs out - why does that not break the proof?
Because the default only fires against machines that are too slow. For a machine inside the smaller time bound, the simulation finishes inside the budget on every sufficiently long encoding of it, so the disagreement happens where it is needed. The default verdict on the remaining inputs costs the argument nothing.
A padding argument shows that if L equalled P then PSPACE would equal EXPTIME. Which inference does that license?
The contrapositive only: proving PSPACE different from EXPTIME would prove L different from P. Padding carries a collapse upward, so it carries a separation downward. Reading it the other way - that separating L from P settles PSPACE versus EXPTIME - inverts the implication and is the usual error.
Does the theorem hold for any pair of growing time bounds?
No. The larger bound must be time-constructible, and the gap must exceed the simulation overhead. For pathological, non-constructible bounds there are ranges in which a larger budget buys no new languages at all, so the hypotheses are doing real work rather than tidying up a statement.

saying these in an interview costs you the question

Says the theorem exhibits a natural problem needing exponential time
Assumes any increase in the time budget buys new languages
Thinks the same diagonal argument settles P versus NP
Expects the space version to need the same logarithmic slack
Reads padding as carrying a separation upward rather than downward

Why does the time hierarchy theorem separate two deterministic time classes when no explicit hard problem is known?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What the theorem claims

The construction: a machine built to disagree

Why time loses a logarithmic factor and space does not

Constructibility, and what happens without it

Padding: lifting a result up the chain

What the theorem does not give you

▾common follow-ups3 questions

▾red flags5 flags

What the theorem claims

The construction: a machine built to disagree

Why time loses a logarithmic factor and space does not

Constructibility, and what happens without it

Padding: lifting a result up the chain

What the theorem does not give you

answer

go deeper