The deterministic time hierarchy theorem for exponential time
Lax119563.ExponentialTimeHierarchy · concepts/Lax119563/ExponentialTimeHierarchy.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Hartmanis and Stearns; Hennie and Stearns: there is a language with
i.e., is decided by a deterministic multitape Turing machine in time , but by no deterministic multitape Turing machine in time .
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Analysis.SpecialFunctions.Pow.Real |
| 2 | import Lax119563.DeterministicTime |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: The deterministic time hierarchy theorem for exponential time |
| 7 | type: theorem |
| 8 | --- |
| 9 | Hartmanis and Stearns; Hennie and Stearns: there is a language |
| 10 | with |
| 11 | |
| 12 | i.e., is decided by a deterministic multitape Turing machine in time , |
| 13 | but by no deterministic multitape Turing machine in time . |
| 14 | |
| 15 | # Implementation notes |
| 16 | This is the exponential instance of the time hierarchy theorem, in the machine model of the |
| 17 | polynomial instance `Lax119563.TimeHierarchy.time_hierarchy` (see there for the choice of the |
| 18 | model). It applies since is time constructible and |
| 19 | . The exponent (rather than the sharper ) leaves room for |
| 20 | a universal machine with polynomial (cubic) overhead, which suffices for the exponential lower |
| 21 | bound. |
| 22 | -/ |
| 23 | |
| 24 | open Lax119563.DeterministicTime |
| 25 | |
| 26 | namespace Lax119563.ExponentialTimeHierarchy |
| 27 | |
| 28 | /-- **The deterministic time hierarchy theorem** for the bounds `2^n` and `2^{n/4}`. -/ |
| 29 | axiom exp_time_hierarchy : |
| 30 | ∃ L : Set (List Bool), |
| 31 | DecidableInTime L (fun n => (2 : ℝ) ^ (n : ℝ)) ∧ |
| 32 | ¬ DecidableInTime L (fun n => (2 : ℝ) ^ ((n : ℝ) / 4)) |
| 33 | |
| 34 | end Lax119563.ExponentialTimeHierarchy |
| 35 |
Implementation notes
This is the exponential instance of the time hierarchy theorem, in the machine model of the polynomial instance (see there for the choice of the model). It applies since is time constructible and . The exponent (rather than the sharper ) leaves room for a universal machine with polynomial (cubic) overhead, which suffices for the exponential lower bound.
Builds on
Used by
none
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments