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.
Description
For , a deterministic decider (from ) is run on padded inputs (); the machine writes with and runs the pipeline machine of . The choice (from the coefficient sum and degree of the polynomial and the constant of the decider) gives , so the decider halts within steps, while and make the running time polynomial. The machine is translated by .