Questions: Space Hierarchy Theorem

Question 1

The space hierarchy theorem guarantees a strict separation between DSPACE(n) and a larger class. What is the minimum space budget that provably contains languages not in DSPACE(n)?

• A. DSPACE(n²) — the same quadratic blowup required by the time hierarchy theorem
• B. DSPACE(n log n) — a logarithmic factor above n is sufficient
• C. DSPACE(2n) — space must double to guarantee new problems
• D. DSPACE(n + 1) — any additional constant suffices

Answer: (B)

The space hierarchy theorem requires only a logarithmic overhead: DSPACE(f(n)) ⊊ DSPACE(f(n) log f(n)). For f(n) = n, this gives DSPACE(n) ⊊ DSPACE(n log n). The logarithmic factor comes from the bookkeeping cost in the diagonalization proof — tracking how many cells a simulated machine has used requires writing a number up to f(n), which takes log f(n) bits. The quadratic blowup is the time hierarchy's requirement, not space's — space is reusable, so the overhead is much tighter.

Question 2

Why does the diagonalization proof of the space hierarchy theorem introduce a log f(n) overhead rather than a constant overhead?

• A. Because the simulator must store the entire tape of the simulated machine
• B. Because writing a counter up to f(n) to track how much space the simulated machine has used requires log f(n) bits
• C. Because the diagonalization argument must iterate over all f(n) possible machines
• D. Because space-constructible functions require logarithmic overhead to compute

Answer: (B)

The simulator needs to enforce the f(n) space bound on the simulated machine. To do this, it must count how many tape cells the simulated machine has used, incrementing a counter for each step. A counter that can reach values up to f(n) requires ⌈log₂ f(n)⌉ bits to store — this is the overhead. The simulator's total space usage is f(n) for the simulated tape plus O(log f(n)) for the counter and bookkeeping, which totals O(f(n) log f(n)). This is why the proven separation requires f(n) log f(n) rather than f(n) + 1.

Question 3

The space hierarchy theorem is an unconditional result — it provides a proven separation between complexity classes, not merely a conjecture.

• T. True
• F. False

Answer: True

This is one of the most important features of the hierarchy theorems. Unlike major open questions in complexity theory (P vs. NP, NL vs. L, etc.), the space and time hierarchy theorems are fully proven. They use diagonalization — a constructive argument that explicitly builds a language lying in the larger class but not the smaller one. No assumption, conjecture, or unproven hypothesis is needed. The theorems give the field a backbone of known, proven separations, even though most other separations remain elusive.

Question 4

Because space is reusable, the space hierarchy theorem requires the same quadratic overhead as the time hierarchy theorem to guarantee a strictly larger complexity class.

• T. True
• F. False

Answer: False

This is the opposite of the correct claim — and the key conceptual insight of the theorem. Because space is reusable (tape cells can be overwritten), the overhead needed in the diagonalization simulation is only logarithmic, not quadratic. The time hierarchy theorem requires quadratic overhead because time steps are consumed permanently: each simulated step costs the simulator a real step, and the overhead accumulates multiplicatively. Space only measures the maximum simultaneous usage, so the bookkeeping (a counter) adds only O(log f(n)) extra cells regardless of how many steps the simulation takes.

Question 5

Why does space reusability cause the space hierarchy theorem to require only a logarithmic overhead, while the time hierarchy theorem requires a quadratic overhead?

Model answer: In the time hierarchy proof, simulating each step of the target machine costs the simulator at least one real step. Overhead from the simulation bookkeeping multiplies the total time, requiring a quadratic factor to guarantee separation. In the space hierarchy proof, the simulator reuses the simulated machine's tape cells — it writes over them repeatedly. The only extra space needed is a counter tracking how many cells have been used, which requires only log f(n) bits. Space measures peak simultaneous usage, not cumulative cost, so overhead doesn't compound — it stays at O(log f(n)) regardless of how long the simulation runs.

The asymmetry between time and space hierarchies reflects a deep difference in how the two resources work. Time is irrecoverable — once spent, it cannot be reused. Space is recoverable — a tape cell used and then overwritten costs nothing more. This makes space a fundamentally 'tighter' resource in the complexity hierarchy, and the theorems reflect this: provably distinct space classes are much closer together (logarithmic gap) than provably distinct time classes (quadratic gap).