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

An unconditional time lower bound for k-WL Distinguishing

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

    The problem kk-WL Distinguishing asks, given two colored graphs GG and HH, whether kk-WL distinguishes GG and HH.

    Theorem. For every fixed k≥3k \geq 3 and ε>0\varepsilon > 0, no deterministic multitape Turing machine solves kk-WL Distinguishing in time O(nk−1−ε)O(n^{k - 1 - \varepsilon}), where nn is the length of the binary encoding of the input pair.

    This almost matches the classical upper bound of O(nk+1log⁡n)O(n^{k+1} \log n).

    Concept map
    7 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.BinaryEncodings
    3import Lax119563.DeterministicTime
    4import Lax119563.WeisfeilerLeman
    5
    6/-!
    7---
    8title: An unconditional time lower bound for k-WL Distinguishing
    9type: theorem
    10---
    11The problem kk-WL Distinguishing asks, given two colored graphs GG and HH,
    12whether kk-WL distinguishes GG and HH.
    13
    14**Theorem.** For every fixed k≥3k \geq 3 and ε>0\varepsilon > 0, no deterministic multitape
    15Turing machine solves kk-WL Distinguishing in time O(nk−1−ε)O(n^{k - 1 - \varepsilon}), where nn is
    16the length of the binary encoding of the input pair.
    17
    18This almost matches the classical upper bound of O(nk+1log⁡n)O(n^{k+1} \log n).
    19
    20# Implementation notes
    21
    22The input graph pair is given by its binary edge-list encoding, and time is measured in the
    23length nn of the encoding `encodeGraphPair G H`. This length is at least the number
    24∣V(G)∣+∣V(H)∣|V(G)| + |V(H)| of vertices, so the statement is stronger than one in terms of vertices,
    25and it also rules out the degenerate case of huge colors, whose codes a machine with a
    26vertex-based budget could not even read. A machine solving the problem in time
    27O(nk−1−ε)O(n^{k-1-\varepsilon}) would, for some constant CC, decide on every encoded pair within
    28Cnk−1−ε+CC n^{k-1-\varepsilon} + C steps whether kk-WL distinguishes it. The machine is not
    29required to handle strings that are not encodings of graph pairs, which only strengthens the
    30lower bound.
    31-/
    32
    33open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.BinaryEncodings
    34 Lax119563.DeterministicTime
    35open Lax489179.TuringMachine (Machine Deterministic)
    36
    37namespace Lax119563.RuntimeLowerBound
    38
    39/-- **Unconditional time lower bound.** For `k ≥ 3` and `ε > 0`, no deterministic multitape
    40Turing machine decides `k`-WL distinguishability of colored graph pairs within
    41`O(n^{k-1-ε})` steps, where `n` is the length of the binary encoding of the input pair. -/
    42axiom runtime_lower_bound (k : ℕ) (hk : 3 ≤ k) (ε : ℝ) (hε : 0 < ε) :
    43 ¬ ∃ M : Machine, Deterministic M ∧ ∃ C : ℕ, ∀ G H : ColoredGraph,
    44 DecidesExactlyWithin M (encodeGraphPair G H) (Distinguishes k G H)
    45 ⌊C * ((encodeGraphPair G H).length : ℝ) ^ ((k : ℝ) - 1 - ε) + C⌋₊
    46
    47end Lax119563.RuntimeLowerBound
    48
    Show Proof

    Implementation notes

    The input graph pair is given by its binary edge-list encoding, and time is measured in the length nn of the encoding encodeGraphPairGHencodeGraphPair G H. This length is at least the number ∣V(G)∣+∣V(H)∣|V(G)| + |V(H)| of vertices, so the statement is stronger than one in terms of vertices, and it also rules out the degenerate case of huge colors, whose codes a machine with a vertex-based budget could not even read. A machine solving the problem in time O(nk−1−ε)O(n^{k-1-\varepsilon}) would, for some constant CC, decide on every encoded pair within Cnk−1−ε+CC n^{k-1-\varepsilon} + C steps whether kk-WL distinguishes it. The machine is not required to handle strings that are not encodings of graph pairs, which only strengthens the lower bound.

    Discussion

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

    Loading discussion…