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

Proof of `An exponential time lower bound for WL Distinguishing`

groundedproofs/Lax119563Proofs/Hardness/ExpLower.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

Let L∈DTIME(2n) DTIME(2n/4)L ∈ DTIME(2^n) \ DTIME(2^{n/4}) be decided by MM within C02n+C0C₀ 2^n + C₀ steps, and put c0=2C0+2c₀ = 2 C₀ + 2. For ∣x∣=n≥2|x| = n ≥ 2, h=n+c0h = n + c₀, a=⌈log2(n+2)⌉a = ⌈log₂(n + 2)⌉ and ss the least number with sa≥h+2s a ≥ h + 2, a machine computes encodeNats[h,s]++xencodeNats [h, s] ++ x in time O(m3)O(m^3) (m=n+c0+4m = n + c₀ + 4), and the pipeline turns it in time mO(1)m^{O(1)} into an instance (s+1,G0,G1)(s + 1, G₀, G₁) of length N≤Bm5N ≤ B m^5 (explenarithexp_len_arith), which (s+1)(s+1)-WL distinguishes iff x∈Lx ∈ L. With ε=1/(4(B+1)1/5)ε = 1 / (4 (B + 1)^{1/5}), a decider for WL Distinguishing within C2εN1/5+CC 2^{ε N^{1/5}} + C steps runs within C2m/4+CC 2^{m/4} + C steps on these instances; together with the polynomial reduction this decides LL in time O(2n/4)O(2^{n/4}), a contradiction.