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

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.

Read the Lean proof on GitHub

Description

For P∈XPP ∈ XP with decider MM in time f(k)(n+1)f(k)f(k) (n + 1)^{f(k)}, let Fk=2f(k)+4F k = 2 f(k) + 4. The reduction machine padTMQpadTM Q writes the padded input y=true::true::xy = true :: true :: x and runs QQ, the composition of withSuffixwithSuffix of the machine of xpSxpS (which computes [h,s][h, s] with h=F(k)⌈log2(∣x∣+4)⌉h = F(k) ⌈log₂ (|x| + 4)⌉ and s=F(k)+1s = F(k) + 1, xpprogxp_prog) with the pipeline machine (pipelinelanguagepipeline_language) of the padded decider. The padded decider halts within (∣x∣+4)Fk≤2h(|x| + 4)^{F k} ≤ 2^h steps (xphaltarithxp_halt_arith), so the pipeline is correct; its running time is polynomial in ∣x∣|x| with a degree independent of kk, since the block width is at most ⌈log2(∣x∣+4)⌉+1⌈log₂ (|x| + 4)⌉ + 1 (xpwidthlexp_width_le, xptotalarithxp_total_arith). The new parameter is s+1=2f(k)+6s + 1 = 2 f(k) + 6.