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

Proof of `WL Distinguishing is EXPTIME-hard`

groundedproofs/Lax119563Proofs/Hardness/Exptime.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 L∈EXPTIMEL ∈ EXPTIME, a deterministic decider (from singleTapesimulationsingleTape_simulation) is run on padded inputs true::true::xtrue :: true :: x (paddeddecidespadded_decides); the machine redTMRdredTM R d writes encodeNats[h,h]++true::true::xencodeNats [h, h] ++ true :: true :: x with h=2(d(∣bitsn∣+1))−1h = 2^(d (|bits n| + 1)) - 1 and runs the pipeline machine RR of pipelinelanguagepipeline_language. The choice d=A+D+B+2d = A + D + B + 2 (from the coefficient sum AA and degree DD of the polynomial and the constant BB of the decider) gives h≥p(n)+n+Bh ≥ p(n) + n + B, so the decider halts within 2h2^h steps, while h+1≤(4(n+1))dh + 1 ≤ (4 (n + 1))^d and 2ℓ≤8(n+1)2^ℓ ≤ 8 (n + 1) make the running time polynomial. The machine is translated by tm2ofpolyTimetm2_of_polyTime.