Proof of `WL Distinguishing is XP-hard`
groundedproofs/Lax119563Proofs/Hardness/Xp.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 with decider in time , let . The reduction machine writes the padded input and runs , the composition of of the machine of (which computes with and , ) with the pipeline machine () of the padded decider. The padded decider halts within steps (), so the pipeline is correct; its running time is polynomial in with a degree independent of , since the block width is at most (, ). The new parameter is .