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

Proof of `An unconditional time lower bound for k-WL Distinguishing`

groundedproofs/Lax119563Proofs/Main/RuntimeLowerBound.lean · lax-119563

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

For k≥3k ≥ 3 and ε>0ε > 0, assume a deterministic machine decides kk-WL distinguishability within CNk−1−ε+CC N^{k-1-ε} + C steps on encoded pairs of length NN. With s=k−1s = k - 1 and ε′=minε1ε' = min ε 1, the time hierarchy theorem gives a language L∈DTIME(ns) DTIME(ns−ε′/2)L ∈ DTIME(n^s) \ DTIME(n^{s - ε'/2}). The reduction maps inputs of length n≥2n ≥ 2 in time t1=O(nlogcn)t₁ = O(n log^c n) to encoded graph pairs of length N≤t1N ≤ t₁ that kk-WL distinguishes exactly for members of LL. Running the reduction, rewinding, and then the fast decider (and answering inputs of length <2< 2 directly) decides LL within 2t1+O(t1k−1−ε′)+O(1)=O(ns−ε′/2)2 t₁ + O(t₁^{k-1-ε'}) + O(1) = O(n^{s - ε'/2}) steps, contradicting the choice of LL.