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

The deterministic time hierarchy theorem for exponential time

Lax119563.ExponentialTimeHierarchy · concepts/Lax119563/ExponentialTimeHierarchy.lean · lax-119563

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Hartmanis and Stearns; Hennie and Stearns: there is a language L⊆{0,1}∗\mathcal L \subseteq \{0, 1\}^* with

    L∈DTIME(2n)∖DTIME(2n/4),\mathcal L \in \mathsf{DTIME}(2^n) \setminus \mathsf{DTIME}(2^{n/4}),

    i.e., L\mathcal L is decided by a deterministic multitape Turing machine in time O(2n)O(2^n), but by no deterministic multitape Turing machine in time O(2n/4)O(2^{n/4}).

    Concept map
    4 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Mathlib.Analysis.SpecialFunctions.Pow.Real
    2import Lax119563.DeterministicTime
    3
    4/-!
    5---
    6title: The deterministic time hierarchy theorem for exponential time
    7type: theorem
    8---
    9Hartmanis and Stearns; Hennie and Stearns: there is a language
    10L⊆{0,1}∗\mathcal L \subseteq \{0, 1\}^* with
    11L∈DTIME(2n)∖DTIME(2n/4),\mathcal L \in \mathsf{DTIME}(2^n) \setminus \mathsf{DTIME}(2^{n/4}),
    12i.e., L\mathcal L is decided by a deterministic multitape Turing machine in time O(2n)O(2^n),
    13but by no deterministic multitape Turing machine in time O(2n/4)O(2^{n/4}).
    14
    15# Implementation notes
    16This is the exponential instance of the time hierarchy theorem, in the machine model of the
    17polynomial instance `Lax119563.TimeHierarchy.time_hierarchy` (see there for the choice of the
    18model). It applies since 2n2^n is time constructible and
    192n/4log⁡2n/4=o(2n)2^{n/4} \log 2^{n/4} = o(2^n). The exponent n/4n/4 (rather than the sharper n/2n/2) leaves room for
    20a universal machine with polynomial (cubic) overhead, which suffices for the exponential lower
    21bound.
    22-/
    23
    24open Lax119563.DeterministicTime
    25
    26namespace Lax119563.ExponentialTimeHierarchy
    27
    28/-- **The deterministic time hierarchy theorem** for the bounds `2^n` and `2^{n/4}`. -/
    29axiom exp_time_hierarchy :
    30 ∃ L : Set (List Bool),
    31 DecidableInTime L (fun n => (2 : ℝ) ^ (n : ℝ)) ∧
    32 ¬ DecidableInTime L (fun n => (2 : ℝ) ^ ((n : ℝ) / 4))
    33
    34end Lax119563.ExponentialTimeHierarchy
    35
    Show Proof

    Implementation notes

    This is the exponential instance of the time hierarchy theorem, in the machine model of the polynomial instance Lax119563.TimeHierarchy.timehierarchyLax119563.TimeHierarchy.time_hierarchy (see there for the choice of the model). It applies since 2n2^n is time constructible and 2n/4log⁡2n/4=o(2n)2^{n/4} \log 2^{n/4} = o(2^n). The exponent n/4n/4 (rather than the sharper n/2n/2) leaves room for a universal machine with polynomial (cubic) overhead, which suffices for the exponential lower bound.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…