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

The deterministic time hierarchy theorem

Lax119563.TimeHierarchy · concepts/Lax119563/TimeHierarchy.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: for every integer s≥1s \geq 1 and every real a<sa < s, there is a language L⊆{0,1}∗\mathcal L \subseteq \{0, 1\}^* with

    L∈DTIME(ns)∖DTIME(na),\mathcal L \in \mathsf{DTIME}(n^s) \setminus \mathsf{DTIME}(n^a),

    i.e., L\mathcal L is decided by a deterministic multitape Turing machine in time O(ns)O(n^s), but by no deterministic multitape Turing machine in time O(na)O(n^a).

    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
    7type: theorem
    8---
    9Hartmanis and Stearns; Hennie and Stearns: for every integer s≥1s \geq 1 and every real
    10a<sa < s, there is a language L⊆{0,1}∗\mathcal L \subseteq \{0, 1\}^* with
    11L∈DTIME(ns)∖DTIME(na),\mathcal L \in \mathsf{DTIME}(n^s) \setminus \mathsf{DTIME}(n^a),
    12i.e., L\mathcal L is decided by a deterministic multitape Turing machine in time O(ns)O(n^s),
    13but by no deterministic multitape Turing machine in time O(na)O(n^a).
    14
    15# Implementation notes
    16
    17The machine model is that of `Lax119563.DeterministicTime`; see there for why the exact
    18exponent of the main lower bound enters here and for the choice of the model.
    19-/
    20
    21open Lax119563.DeterministicTime
    22
    23namespace Lax119563.TimeHierarchy
    24
    25/-- **The deterministic time hierarchy theorem** for polynomial time bounds. -/
    26axiom time_hierarchy (s : ℕ) (hs : 1 ≤ s) (a : ℝ) (ha : a < s) :
    27 ∃ L : Set (List Bool),
    28 DecidableInTime L (fun n => (n : ℝ) ^ s) ∧ ¬ DecidableInTime L (fun n => (n : ℝ) ^ a)
    29
    30end Lax119563.TimeHierarchy
    31
    Show Proof

    Implementation notes

    The machine model is that of Lax119563.DeterministicTimeLax119563.DeterministicTime; see there for why the exact exponent of the main lower bound enters here and for the choice of the model.

    Discussion

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

    Loading discussion…