An unconditional time lower bound for k-WL Distinguishing
Lax119563.RuntimeLowerBound · concepts/Lax119563/RuntimeLowerBound.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The problem -WL Distinguishing asks, given two colored graphs and , whether -WL distinguishes and .
Theorem. For every fixed and , no deterministic multitape Turing machine solves -WL Distinguishing in time , where is the length of the binary encoding of the input pair.
This almost matches the classical upper bound of .
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Mathlib.Analysis.SpecialFunctions.Pow.Real |
| 2 | import Lax119563.BinaryEncodings |
| 3 | import Lax119563.DeterministicTime |
| 4 | import Lax119563.WeisfeilerLeman |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: An unconditional time lower bound for k-WL Distinguishing |
| 9 | type: theorem |
| 10 | --- |
| 11 | The problem -WL Distinguishing asks, given two colored graphs and , |
| 12 | whether -WL distinguishes and . |
| 13 | |
| 14 | **Theorem.** For every fixed and , no deterministic multitape |
| 15 | Turing machine solves -WL Distinguishing in time , where is |
| 16 | the length of the binary encoding of the input pair. |
| 17 | |
| 18 | This almost matches the classical upper bound of . |
| 19 | |
| 20 | # Implementation notes |
| 21 | |
| 22 | The input graph pair is given by its binary edge-list encoding, and time is measured in the |
| 23 | length of the encoding `encodeGraphPair G H`. This length is at least the number |
| 24 | of vertices, so the statement is stronger than one in terms of vertices, |
| 25 | and it also rules out the degenerate case of huge colors, whose codes a machine with a |
| 26 | vertex-based budget could not even read. A machine solving the problem in time |
| 27 | would, for some constant , decide on every encoded pair within |
| 28 | steps whether -WL distinguishes it. The machine is not |
| 29 | required to handle strings that are not encodings of graph pairs, which only strengthens the |
| 30 | lower bound. |
| 31 | -/ |
| 32 | |
| 33 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.BinaryEncodings |
| 34 | Lax119563.DeterministicTime |
| 35 | open Lax489179.TuringMachine (Machine Deterministic) |
| 36 | |
| 37 | namespace Lax119563.RuntimeLowerBound |
| 38 | |
| 39 | /-- **Unconditional time lower bound.** For `k ≥ 3` and `ε > 0`, no deterministic multitape |
| 40 | Turing 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. -/ |
| 42 | axiom 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 | |
| 47 | end Lax119563.RuntimeLowerBound |
| 48 |
Implementation notes
The input graph pair is given by its binary edge-list encoding, and time is measured in the length of the encoding . This length is at least the number 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 would, for some constant , decide on every encoded pair within steps whether -WL distinguishes it. The machine is not required to handle strings that are not encodings of graph pairs, which only strengthens the lower bound.
Used by
none
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments