The Time & Space Hierarchies

Give a computer a faster clock or a bigger memory and, obviously, it can do more — right? It turns out that "obviously" hides one of the most elegant proven results in computer science.

The time hierarchy theorem and the space hierarchy theorem say that the gain is real and strict: there are problems you simply cannot solve in, say, $n^{2}$ steps, yet you can solve once you are allowed $n^{3}$. The same goes for memory — a little more workspace unlocks languages that were genuinely out of reach before.

This is not a claim about clever programmers being lazy. It is a hard mathematical line: with a tiny bit more of the right resource, the set of solvable problems gets strictly bigger. No algorithm, however ingenious, can cross that line from below.

Below is a toy "machine" that must finish each input within a step budget that grows with the input size n. You pick the budget's growth rate — linear (n), quadratic ($n^{2}$) or cubic ($n^{3}$) — and the machine runs a task that genuinely needs about $n^{2}$ · log n steps.

<p class="hint">The machine runs a real task on each input that costs about
<b>n²·log&#8322;n</b> steps. Pick how fast the <b>step budget</b> may grow, then run.
An input is <b>solved</b> if it finishes inside the budget; otherwise it
<b>times out</b>. Raise the budget and watch timed-out inputs become solvable.</p>
<div class="controls">
  <label>Budget growth:
    <select id="rate">
      <option value="lin">linear&nbsp;&nbsp;(8·n)</option>
      <option value="quad">quadratic&nbsp;&nbsp;(8·n²)</option>
      <option value="cube" selected>cubic&nbsp;&nbsp;(8·n³)</option>
    </select>
  </label>
  <button id="run" type="button">Run the machine</button>
</div>
<table class="grid" id="grid"></table>
<div class="status" id="status">Choose a budget and press Run.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.controls { display: flex; gap: .6rem; align-items: center; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; font-weight: 600; display: flex; gap: .4rem; align-items: center; }
select { font: 600 14px system-ui, sans-serif; padding: .35rem .5rem; border-radius: 8px; border: 1px solid #adb1b8; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
table.grid { border-collapse: collapse; width: 100%; font-size: .9rem; margin: .3rem 0; }
.grid th, .grid td { border: 1px solid #cdd9e3; padding: .4rem .5rem; text-align: right; }
.grid th { background: #e8eef3; color: #1d3557; }
.grid td.lbl { text-align: left; font-weight: 600; }
tr.ok td { background: #e7f6ec; }
tr.bad td { background: #fdecec; }
.tag { font-weight: 700; }
.tag.ok { color: #0a7d33; }
.tag.bad { color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The time hierarchy theorem (Hartmanis & Stearns, 1965): a problem can need
// strictly more time than a smaller budget allows. Here a fixed task costs about
// n^2 * log2(n) "steps". We measure the REAL step count, then compare it to a
// budget that grows linearly, quadratically or cubically. For large n the
// task overruns a linear/quadratic budget but always fits a cubic one — so
// raising the resource strictly enlarges the set of solvable inputs.
const SIZES = [2, 4, 6, 8, 12, 16];
const C = 8; // budget constant, same across rates for a fair comparison

// Run the actual task and count steps performed. Cost ~ n^2 * log2(n).
function runTask(n){
  let steps = 0, acc = 0;
  const passes = Math.max(1, Math.ceil(Math.log2(n))); // ~log2(n) passes
  for(let p = 0; p < passes; p++)
    for(let i = 0; i < n; i++)
      for(let j = 0; j < n; j++){ steps++; acc = (acc + i*j + p) % 1000003; }
  return { steps, acc };
}
function budget(rate, n){
  if(rate === 'lin')  return C * n;
  if(rate === 'quad') return C * n * n;
  return C * n * n * n; // cube
}

function run(){
  const rate = document.getElementById('rate').value;
  const rows = [];
  let solved = 0;
  for(const n of SIZES){
    const { steps } = runTask(n);
    const b = budget(rate, n);
    const ok = steps <= b;
    if(ok) solved++;
    rows.push({ n, steps, b, ok });
  }
  const grid = document.getElementById('grid');
  let html = '<tr><th class="lbl">input size n</th><th>steps needed (~n²·log n)</th><th>budget</th><th>result</th></tr>';
  for(const r of rows){
    const cls = r.ok ? 'ok' : 'bad';
    const tag = r.ok ? '<span class="tag ok">solved</span>' : '<span class="tag bad">timed out</span>';
    html += `<tr class="${cls}"><td class="lbl">n = ${r.n}</td><td>${r.steps.toLocaleString()}</td><td>${r.b.toLocaleString()}</td><td>${tag}</td></tr>`;
  }
  grid.innerHTML = html;
  const s = document.getElementById('status');
  s.className = 'status ok';
  s.textContent = fmt('Budget = %rate%: %solved% of %length% inputs solved within budget.', { rate: rate, solved: solved, length: SIZES.length });
  console.log('rate', rate, 'solved', solved, 'of', SIZES.length, rows);
}
document.getElementById('run').addEventListener('click', run);
run();

<p class="hint">The machine runs a real task on each input that costs about
<b>n²·log&#8322;n</b> steps. Pick how fast the <b>step budget</b> may grow, then run.
An input is <b>solved</b> if it finishes inside the budget; otherwise it
<b>times out</b>. Raise the budget and watch timed-out inputs become solvable.</p>
<div class="controls">
  <label>Budget growth:
    <select id="rate">
      <option value="lin">linear&nbsp;&nbsp;(8·n)</option>
      <option value="quad">quadratic&nbsp;&nbsp;(8·n²)</option>
      <option value="cube" selected>cubic&nbsp;&nbsp;(8·n³)</option>
    </select>
  </label>
  <button id="run" type="button">Run the machine</button>
</div>
<table class="grid" id="grid"></table>
<div class="status" id="status">Choose a budget and press Run.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.controls { display: flex; gap: .6rem; align-items: center; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; font-weight: 600; display: flex; gap: .4rem; align-items: center; }
select { font: 600 14px system-ui, sans-serif; padding: .35rem .5rem; border-radius: 8px; border: 1px solid #adb1b8; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
table.grid { border-collapse: collapse; width: 100%; font-size: .9rem; margin: .3rem 0; }
.grid th, .grid td { border: 1px solid #cdd9e3; padding: .4rem .5rem; text-align: right; }
.grid th { background: #e8eef3; color: #1d3557; }
.grid td.lbl { text-align: left; font-weight: 600; }
tr.ok td { background: #e7f6ec; }
tr.bad td { background: #fdecec; }
.tag { font-weight: 700; }
.tag.ok { color: #0a7d33; }
.tag.bad { color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The time hierarchy theorem (Hartmanis & Stearns, 1965): a problem can need
// strictly more time than a smaller budget allows. Here a fixed task costs about
// n^2 * log2(n) "steps". We measure the REAL step count, then compare it to a
// budget that grows linearly, quadratically or cubically. For large n the
// task overruns a linear/quadratic budget but always fits a cubic one — so
// raising the resource strictly enlarges the set of solvable inputs.
const SIZES = [2, 4, 6, 8, 12, 16];
const C = 8; // budget constant, same across rates for a fair comparison

// Run the actual task and count steps performed. Cost ~ n^2 * log2(n).
function runTask(n){
  let steps = 0, acc = 0;
  const passes = Math.max(1, Math.ceil(Math.log2(n))); // ~log2(n) passes
  for(let p = 0; p < passes; p++)
    for(let i = 0; i < n; i++)
      for(let j = 0; j < n; j++){ steps++; acc = (acc + i*j + p) % 1000003; }
  return { steps, acc };
}
function budget(rate, n){
  if(rate === 'lin')  return C * n;
  if(rate === 'quad') return C * n * n;
  return C * n * n * n; // cube
}

function run(){
  const rate = document.getElementById('rate').value;
  const rows = [];
  let solved = 0;
  for(const n of SIZES){
    const { steps } = runTask(n);
    const b = budget(rate, n);
    const ok = steps <= b;
    if(ok) solved++;
    rows.push({ n, steps, b, ok });
  }
  const grid = document.getElementById('grid');
  let html = '<tr><th class="lbl">input size n</th><th>steps needed (~n²·log n)</th><th>budget</th><th>result</th></tr>';
  for(const r of rows){
    const cls = r.ok ? 'ok' : 'bad';
    const tag = r.ok ? '<span class="tag ok">solved</span>' : '<span class="tag bad">timed out</span>';
    html += `<tr class="${cls}"><td class="lbl">n = ${r.n}</td><td>${r.steps.toLocaleString()}</td><td>${r.b.toLocaleString()}</td><td>${tag}</td></tr>`;
  }
  grid.innerHTML = html;
  const s = document.getElementById('status');
  s.className = 'status ok';
  s.textContent = fmt('Budget = %rate%: %solved% of %length% inputs solved within budget.', { rate: rate, solved: solved, length: SIZES.length });
  console.log('rate', rate, 'solved', solved, 'of', SIZES.length, rows);
}
document.getElementById('run').addEventListener('click', run);
run();

Watch the asymmetry. With a linear budget many inputs time out — the machine literally cannot finish. Bump the budget up to cubic and those very same inputs now complete with room to spare. The set of "solvable within budget" inputs grew strictly larger just because the resource did. That little jump is the hierarchy theorem in miniature. See it pushed to the extreme in the exponential time hypothesis.

How do we know more resources strictly help? Not by trying hard and failing — by proof.

• Status: proven. The time hierarchy theorem was established by Juris Hartmanis and Richard Stearns in 1965 (the work that opened the field and won them the 1993 Turing Award). The space hierarchy theorem came the same year from Stearns, Hartmanis and Philip Lewis.
• Time version: if f and g are reasonable ("time-constructible") bounds and f grows enough faster than g (precisely, g · log g is o(f)), then there is a language decidable in time f(n) but not in time g(n). So DTIME($n^{2}$) ⊊ DTIME($n^{3}$), strictly.
• Space version: it is even sharper. If g is o(f) and f is space-constructible, then there is a language decidable in space f(n) but not g(n) — no logarithmic gap needed. So DSPACE(log n) ⊊ DSPACE($\log ^{2}$ n), strictly.
• The trick is diagonalization. Build a machine D that, given the code of a machine M, simulates M on its own description for the larger budget and then outputs the opposite answer. D needs slightly more resource to run the simulation, but by construction it disagrees with every machine that runs cheaper — so its language cannot live in the smaller class.

This is the same self-referential move behind the halting problem: point a machine at itself and force a contradiction. Here the payoff is positive — a guarantee that the complexity classes form a genuine, infinite staircase, not one big flat plateau.

The hierarchies sound abstract, but they are the bedrock the rest of complexity theory stands on:

• They prove classes are different at all. Without them you couldn't even be sure that P (polynomial time) differs from EXPTIME (exponential time). The time hierarchy theorem gives that separation outright: P ⊊ EXPTIME, proven.
• They make "harder problem" mean something. Saying a problem needs more time is only meaningful because more time really does buy more — otherwise every class would collapse into one.
• They anchor open questions. Famous unknowns like P vs NP are hard precisely because the easy diagonalization that works here provably cannot settle them (the "relativization barrier"). Knowing what the technique can and can't do shapes the whole research program.
• They justify engineering trade-offs. Time-versus-space results such as Savitch's theorem live in the world the hierarchies define, where spending one resource to save another is a precise, quantifiable bargain.

In short: every time someone says one problem is "strictly harder" than another, they are leaning on the staircase these theorems built.

The time and space hierarchy theorems deliver a rare thing in this field: a clean, proven yes. More time strictly helps. More space strictly helps. The classes do not collapse — they rise in an endless staircase, each step holding problems forever out of reach of the steps below it.

So the next time you wish your program had a little more room or a little more clock, take heart — that wish is grounded in a theorem. And when you meet a problem that seems impossibly hard, remember that the very tool which proves these floors exist runs out of road at P vs NP. The staircase is real; how high our hardest problems sit on it is still one of the great open questions.