Lax Lean Archive

The inclusion chain of complexity classes

Lax434930.BasicProperties · concepts/Lax434930/BasicProperties.lean · lax-434930

proven

Loading review…

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

    The classical classes satisfy L⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXPTIME\mathrm{L}\subseteq\mathrm{NL}\subseteq\mathrm{P}\subseteq\mathrm{NP} \subseteq\mathrm{PSPACE}=\mathrm{NPSPACE}\subseteq\mathrm{EXPTIME}.

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

    This concept declares 5 statements. Each proof establishes one of them relative to its assumptions.

    1 L_subset_NL proven

    2 NL_subset_P proven

    3 NP_subset_PSPACE proven

    4 NPSPACE_subset_EXPTIME proven

    5 P_subset_NP proven

    In the paper

    • page 4 of this submission's paper
    • page 4 of this submission's paper
    • page 4 of this submission's paper
    • page 4 of this submission's paper
    • page 5 of this submission's paper
    • page 5 of this submission's paper

    Lean source view on GitHub

    1import Lax434930.LogarithmicSpace
    2import Lax434930.NondeterministicLogarithmicSpace
    3import Lax434930.PolynomialSpace
    4import Lax434930.NondeterministicPolynomialSpace
    5import Lax434930.ComplementClasses
    6import Lax434930.ExponentialTime
    7import Lax434930.PolynomialSpaceEquality
    8
    9/-!
    10---
    11title: The inclusion chain of complexity classes
    12type: theorem
    13---
    14The classical classes satisfy
    15L⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXPTIME\mathrm{L}\subseteq\mathrm{NL}\subseteq\mathrm{P}\subseteq\mathrm{NP} \subseteq\mathrm{PSPACE}=\mathrm{NPSPACE}\subseteq\mathrm{EXPTIME}
    16.
    17-/
    18
    19namespace Lax434930.BasicProperties
    20
    21open PolynomialTime LogarithmicSpace NondeterministicLogarithmicSpace
    22open NondeterministicPolynomialTime PolynomialSpace NondeterministicPolynomialSpace
    23open ExponentialTime
    24
    25axiom L_subset_NL : L ⊆ NL
    26
    27axiom NL_subset_P : NL ⊆ P
    28
    29axiom P_subset_NP : P ⊆ NP
    30
    31axiom NP_subset_PSPACE : NP ⊆ PSPACE
    32
    33axiom NPSPACE_subset_EXPTIME : NPSPACE ⊆ EXPTIME
    34
    35end Lax434930.BasicProperties
    36
    Show ProofShow ProofShow ProofShow ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…