An exponential time lower bound for WL Distinguishing
Lax119563.ExponentialLowerBound · concepts/Lax119563/ExponentialLowerBound.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Corollary
Corollary. There is a constant such that no deterministic multitape Turing machine decides WL Distinguishing in time , where is the length of the input.
The proof applies the reduction from exponential time to a language in : for inputs of length it produces graphs with vertices in polynomial time, and the encoded instance has polynomial length.
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.DeterministicTime |
| 3 | import Lax119563.WLProblems |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: An exponential time lower bound for WL Distinguishing |
| 8 | type: corollary |
| 9 | --- |
| 10 | **Corollary.** There is a constant such that no deterministic multitape |
| 11 | Turing machine decides WL Distinguishing in time , |
| 12 | where is the length of the input. |
| 13 | |
| 14 | The proof applies the reduction from exponential time to a language in |
| 15 | : for inputs of length it produces |
| 16 | graphs with vertices in polynomial time, and the encoded instance has |
| 17 | polynomial length. |
| 18 | |
| 19 | # Implementation notes |
| 20 | The input is the instance in the encoding `encodeWLInstance` of |
| 21 | `Lax119563.WLProblems`, with the dimension part of the input, and is the length of |
| 22 | `encodeWLInstance k G H`. Measuring in the input length rather than in the number of vertices |
| 23 | makes the statement stronger, and it accounts for the codes of and of the colors, which a |
| 24 | machine with a budget in the number of vertices could not even read. A machine deciding the |
| 25 | problem in time would, for some constant , decide on every |
| 26 | encoded instance within steps whether -WL distinguishes |
| 27 | and . As in `Lax119563.RuntimeLowerBound`, the machine is not |
| 28 | required to handle other strings. |
| 29 | -/ |
| 30 | |
| 31 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.DeterministicTime |
| 32 | Lax119563.WLProblems |
| 33 | open Lax489179.TuringMachine (Machine Deterministic) |
| 34 | |
| 35 | namespace Lax119563.ExponentialLowerBound |
| 36 | |
| 37 | /-- **Exponential time lower bound.** For some `ε > 0`, no deterministic multitape Turing |
| 38 | machine decides WL Distinguishing on encoded instances of length `N` within |
| 39 | `O(2^{ε N^{1/5}})` steps. -/ |
| 40 | axiom 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 | |
| 46 | end Lax119563.ExponentialLowerBound |
| 47 |
Implementation notes
The input is the instance in the encoding of , with the dimension part of the input, and is the length of . Measuring in the input length rather than in the number of vertices makes the statement stronger, and it accounts for the codes of 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 would, for some constant , decide on every encoded instance within steps whether -WL distinguishes and . As in , the machine is not required to handle other strings.
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