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.
Description
For and , assume a deterministic machine decides -WL distinguishability within steps on encoded pairs of length . With and , the time hierarchy theorem gives a language . The reduction maps inputs of length in time to encoded graph pairs of length that -WL distinguishes exactly for members of . Running the reduction, rewinding, and then the fast decider (and answering inputs of length directly) decides within steps, contradicting the choice of .