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

WL Distinguishing is XP-hard

Lax119563.XPHardness · concepts/Lax119563/XPHardness.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, parameterized by the dimension kk, is XP\mathsf{XP}-hard under fpt-reductions: every problem in XP\mathsf{XP} fpt-reduces to it, with a dimension bounded by a computable function of the parameter.

    The reduction builds the packed implicit parity system of a run of a decider of the problem and applies the matrix compiler.

    Concept map
    12 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 Lax119563.ParameterizedComplexity
    2import Lax119563.WLProblems
    3
    4/-!
    5---
    6title: WL Distinguishing is XP-hard
    7type: theorem
    8---
    9**Theorem.** WL Distinguishing, parameterized by the dimension kk, is
    10XP\mathsf{XP}-hard under fpt-reductions: every problem in XP\mathsf{XP} fpt-reduces to it,
    11with a dimension bounded by a computable function of the parameter.
    12
    13The reduction builds the packed implicit parity system of a run of a decider of the problem
    14and applies the matrix compiler.
    15
    16# Implementation notes
    17* XP\mathsf{XP} and fpt-reductions are those of `Lax119563.ParameterizedComplexity`, with
    18 deterministic multitape machines.
    19* The parameterized problem is `Lax119563.WLProblems.paramWLProblem`.
    20-/
    21
    22open Lax119563.WLProblems Lax119563.ParameterizedComplexity
    23
    24namespace Lax119563.XPHardness
    25
    26/-- **XP-hardness.** Every problem in XP fpt-reduces to WL Distinguishing parameterized by the
    27dimension. -/
    28axiom wl_xp_hard : ∀ P ∈ XP, FptReduces P paramWLProblem
    29
    30end Lax119563.XPHardness
    31
    Show Proof

    Implementation notes

    • XP\mathsf{XP} and fpt-reductions are those of Lax119563.ParameterizedComplexityLax119563.ParameterizedComplexity, with deterministic multitape machines.
    • The parameterized problem is Lax119563.WLProblems.paramWLProblemLax119563.WLProblems.paramWLProblem.
    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…