While this submission is a draft, it cannot be used by other submissions.

Proof of `The deterministic time hierarchy theorem`

groundedproofs/Lax119563Proofs/Hierarchy/Main.lean · lax-119563

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The proof uses translation (padding) to reduce the claim to a coarse hierarchy: DTIME(n3b+3)DTIME(n^{3b+3}) is not contained in DTIME(nb)DTIME(n^b). The coarse hierarchy follows from a diagonal argument. A universal stack program simulates the machine whose code is a prefix of the input, with polynomial overhead, under a clock of n3b+3n^{3b+3} steps. The case s=1s = 1 is handled directly: a machine running in time o(n)o(n) cannot read the last input bit.