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

Proof of `The deterministic time hierarchy theorem for exponential time`

groundedproofs/Lax119563Proofs/Hierarchy/ExpMain.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

A diagonal argument. The diagonal machine computes a clock of 2n2^n units on inputs of length nn by doubling a unary counter nn times (in time O(2n)O(2^n)), and runs the universal stack program under this clock; the universal program answers the negation of the machine whose code is a prefix of the input. So the diagonal language is in DTIME(2n)DTIME(2^n). The universal program has cubic overhead: simulating TT steps on inputs of length nn costs O(n2T3)O(n^2 T^3) (with a constant depending on the simulated machine). A machine running within C2n/4+CC 2^{n/4} + C steps is thus simulated within O(n223n/4)≤2nO(n^2 2^{3n/4}) ≤ 2^n steps on long inputs codeM++0kcode M ++ 0^k, where the diagonal machine answers differently.