A theorist claims that DSPACE(n) = DSPACE(n²) — that any language decidable in O(n²) space is also decidable in O(n) space. What does the space hierarchy theorem imply about this claim?
AThe claim might be true — hierarchy theorems only apply to superpolynomial gaps, not polynomial ones like n vs n²
BThe claim is provably false — since n = o(n²) and both functions are space-constructible, the theorem guarantees DSPACE(n) ⊊ DSPACE(n²) with a witness language
CThe claim requires first verifying whether n and n² are space-constructible, which is an open problem
DThe claim contradicts the P ≠ NP conjecture rather than the space hierarchy theorem
The space hierarchy theorem applies whenever f = o(g) (f grows strictly slower than g asymptotically) and both are space-constructible. Since n/n² → 0, we have n = o(n²), and both n and n² are straightforwardly space-constructible. The theorem directly gives DSPACE(n) ⊊ DSPACE(n²): there exists a language decidable in O(n²) space but provably not in O(n) space, no matter how clever the algorithm. No condition about superpolynomial gaps is needed — any strict asymptotic separation suffices.
Question 2 Multiple Choice
Why does the space hierarchy theorem require no logarithmic slack, unlike the time hierarchy theorem which requires g(n) = Ω(f(n) log f(n))?
ASpace-constructible functions grow faster than time-constructible ones, so the gap is automatically large enough
BUniversal simulation of a Turing machine incurs only a constant space overhead because space can be reused, whereas time simulation requires O(log t) overhead to track the simulated machine's state
CThe diagonalization technique is fundamentally more powerful for space than for time
DThe logarithmic factor in the time hierarchy is an artifact of single-tape versus multi-tape machines, not a real overhead
Simulating a Turing machine on a universal TM incurs O(log t) time overhead because the UTM must track the simulated machine's tape head position step by step — each bookkeeping operation costs logarithmic time. Space simulation is more efficient: you keep a space counter (using O(log s) additional space, a constant relative factor), and the simulated machine's space is reused directly. This constant-factor overhead in space (not logarithmic) is why the space hierarchy gives tighter separations: DSPACE(n) ⊊ DSPACE(n²) follows immediately with no extra slack required.
Question 3 True / False
The strict containment L ⊊ PSPACE is an unconditional theorem — proven, not merely conjectured.
TTrue
FFalse
Answer: True
This follows directly from the space hierarchy theorem. L = DSPACE(log n) and PSPACE contains DSPACE(n) (among many others). Since log n = o(n), the space hierarchy theorem gives DSPACE(log n) ⊊ DSPACE(n) ⊆ PSPACE, so L ⊊ PSPACE is proven. This stands in sharp contrast to inclusions like P ⊆ NP ⊆ PSPACE, where the strictness of individual inclusions remains open and unproven.
Question 4 True / False
The space hierarchy theorem and the P ≠ NP conjecture are both unconditional separations — proven theorems that require no unresolved assumptions.
TTrue
FFalse
Answer: False
The space hierarchy theorem IS an unconditional theorem — it is proven by a clean diagonalization argument with no unresolved hypotheses. P ≠ NP is NOT proven; it is one of the most famous open problems in mathematics and computer science (a Millennium Prize problem worth $1 million). This contrast illustrates precisely why the space hierarchy theorem is significant: it is one of the few places in complexity theory where strict resource separations are provably established rather than conjectured.
Question 5 Short Answer
The space hierarchy proof constructs a diagonalizer M that witnesses DSPACE(f) ⊊ DSPACE(g). Describe how M works and why self-reference is essential to the argument.
Think about your answer, then reveal below.
Model answer: M takes input ⟨e, x⟩, simulates the e-th Turing machine on x while tracking space usage (staying within g(n) space), and outputs the opposite of what the e-th machine would output. When M is given its own encoding as input, it is designed to disagree with the e-th machine at that input — so no f(n)-space machine matches M's behavior on all inputs. M itself uses g(n) space, so the language it accepts is in DSPACE(g) but not DSPACE(f). Self-reference is essential: the diagonal witness is constructed by making M explicitly flip the output of the machine whose description is the input.
Diagonalization produces an object that 'escapes every item on a list' by using that list within its own construction. Here, the 'list' is all f(n)-space Turing machines (enumerated by their encodings), and M 'differs from the e-th entry' by flipping the e-th machine's answer on the input that encodes the e-th machine. This is the same self-referential structure as Cantor's diagonal argument and the undecidability proof for the halting problem — using the object's own description as input to guarantee disagreement.