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

An exponential time lower bound for WL Distinguishing

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

    Corollary

    Corollary. There is a constant ε>0\varepsilon > 0 such that no deterministic multitape Turing machine decides WL Distinguishing in time O(2εN1/5)O(2^{\varepsilon N^{1/5}}), where NN is the length of the input.

    The proof applies the reduction from exponential time to a language in DTIME(2n)∖DTIME(2n/4)\mathsf{DTIME}(2^n) \setminus \mathsf{DTIME}(2^{n/4}): for inputs of length nn it produces graphs with O(n5/log⁡n)O(n^5 / \log n) vertices in polynomial time, and the encoded instance has polynomial length.

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

    Lean source view on GitHub

    1import Mathlib.Analysis.SpecialFunctions.Pow.Real
    2import Lax119563.DeterministicTime
    3import Lax119563.WLProblems
    4
    5/-!
    6---
    7title: An exponential time lower bound for WL Distinguishing
    8type: corollary
    9---
    10**Corollary.** There is a constant ε>0\varepsilon > 0 such that no deterministic multitape
    11Turing machine decides WL Distinguishing in time O(2εN1/5)O(2^{\varepsilon N^{1/5}}),
    12where NN is the length of the input.
    13
    14The proof applies the reduction from exponential time to a language in
    15DTIME(2n)∖DTIME(2n/4)\mathsf{DTIME}(2^n) \setminus \mathsf{DTIME}(2^{n/4}): for inputs of length nn it produces
    16graphs with O(n5/log⁡n)O(n^5 / \log n) vertices in polynomial time, and the encoded instance has
    17polynomial length.
    18
    19# Implementation notes
    20The input is the instance (k,G,H)(k, G, H) in the encoding `encodeWLInstance` of
    21`Lax119563.WLProblems`, with the dimension kk part of the input, and NN is the length of
    22`encodeWLInstance k G H`. Measuring in the input length rather than in the number of vertices
    23makes the statement stronger, and it accounts for the codes of kk and of the colors, which a
    24machine with a budget in the number of vertices could not even read. A machine deciding the
    25problem in time O(2εN1/5)O(2^{\varepsilon N^{1/5}}) would, for some constant CC, decide on every
    26encoded instance within C2εN1/5+CC 2^{\varepsilon N^{1/5}} + C steps whether kk-WL distinguishes
    27GG and HH. As in `Lax119563.RuntimeLowerBound`, the machine is not
    28required to handle other strings.
    29-/
    30
    31open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.DeterministicTime
    32 Lax119563.WLProblems
    33open Lax489179.TuringMachine (Machine Deterministic)
    34
    35namespace Lax119563.ExponentialLowerBound
    36
    37/-- **Exponential time lower bound.** For some `ε > 0`, no deterministic multitape Turing
    38machine decides WL Distinguishing on encoded instances of length `N` within
    39`O(2^{ε N^{1/5}})` steps. -/
    40axiom exponential_lower_bound :
    41 ∃ ε : ℝ, 0 < ε ∧ ¬ ∃ M : Machine, Deterministic M ∧ ∃ C : ℕ,
    42 ∀ (k : ℕ) (G H : ColoredGraph),
    43 DecidesExactlyWithin M (encodeWLInstance k G H) (Distinguishes k G H)
    44 ⌊C * (2 : ℝ) ^ (ε * ((encodeWLInstance k G H).length : ℝ) ^ ((1 : ℝ) / 5)) + C⌋₊
    45
    46end Lax119563.ExponentialLowerBound
    47
    Show Proof

    Implementation notes

    The input is the instance (k,G,H)(k, G, H) in the encoding encodeWLInstanceencodeWLInstance of Lax119563.WLProblemsLax119563.WLProblems, with the dimension kk part of the input, and NN is the length of encodeWLInstancekGHencodeWLInstance k G H. Measuring in the input length rather than in the number of vertices makes the statement stronger, and it accounts for the codes of kk and of the colors, which a machine with a budget in the number of vertices could not even read. A machine deciding the problem in time O(2εN1/5)O(2^{\varepsilon N^{1/5}}) would, for some constant CC, decide on every encoded instance within C2εN1/5+CC 2^{\varepsilon N^{1/5}} + C steps whether kk-WL distinguishes GG and HH. As in Lax119563.RuntimeLowerBoundLax119563.RuntimeLowerBound, the machine is not required to handle other strings.

    Discussion

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

    Loading discussion…