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

WL Distinguishing is EXPTIME-hard

Lax119563.EXPTIMEHardness · concepts/Lax119563/EXPTIMEHardness.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

    Theorem. WL Distinguishing is EXPTIME\mathsf{EXPTIME}-hard under polynomial-time many-one reductions: every language decided by a deterministic machine in time 2p(n)2^{p(n)} reduces in polynomial time to WL Distinguishing.

    The reduction builds the packed implicit parity system of a run of the machine and applies the matrix compiler; the dimension grows with the input.

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

    Lean source view on GitHub

    1import Lax429075.Reductions
    2import Lax119563.WLProblems
    3
    4/-!
    5---
    6title: WL Distinguishing is EXPTIME-hard
    7type: theorem
    8---
    9**Theorem.** WL Distinguishing is EXPTIME\mathsf{EXPTIME}-hard under polynomial-time
    10many-one reductions: every language decided by a deterministic machine in time 2p(n)2^{p(n)}
    11reduces in polynomial time to WL Distinguishing.
    12
    13The reduction builds the packed implicit parity system of a run of the machine and applies
    14the matrix compiler; the dimension grows with the input.
    15
    16# Implementation notes
    17* EXPTIME\mathsf{EXPTIME} is the archive's `Lax434930.ExponentialTime.EXPTIME` (single-tape
    18 machines), and polynomial-time many-one reductions are `Lax429075.Reductions.ManyOne`
    19 (multi-stack machines in polynomial time).
    20* The language is `Lax119563.WLProblems.WLDistinguishing`, with the dimension kk part of the
    21 input.
    22-/
    23
    24open Lax434930.ExponentialTime Lax429075.Reductions
    25open Lax119563.WLProblems
    26
    27namespace Lax119563.EXPTIMEHardness
    28
    29/-- **EXPTIME-hardness.** Every language in EXPTIME reduces in polynomial time to WL
    30Distinguishing. -/
    31axiom wl_exptime_hard : ∀ L ∈ EXPTIME, ManyOne L WLDistinguishing
    32
    33end Lax119563.EXPTIMEHardness
    34
    Show Proof

    Implementation notes

    • EXPTIME\mathsf{EXPTIME} is the archive's Lax434930.ExponentialTime.EXPTIMELax434930.ExponentialTime.EXPTIME (single-tape machines), and polynomial-time many-one reductions are Lax429075.Reductions.ManyOneLax429075.Reductions.ManyOne (multi-stack machines in polynomial time).
    • The language is Lax119563.WLProblems.WLDistinguishingLax119563.WLProblems.WLDistinguishing, with the dimension kk part of the input.
    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…