Proof of `Hitting Set Is W[2]-Complete` (2nd statement)

groundedproofs/Lax496464Proofs/WHierarchy/Lemmas/PiTwoToMonotone/Final.lean · lax-496464

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

p−WDφ≤fptp−WSat(monotoneCNF)p-WD_φ ≤fpt p-WSat(monotone CNF) for every Π2Π₂-sentence φ = ∀ x̄ ∃ ȳ ψ (Flum–Grohe, Theorem 7.1(1) for t=2t = 2, via Lemma 7.2 and the Propositional Normalization Lemma 7.5). The monotone formula has a variable for every block of DD slots with values (DD fixed by ψψ), forces one value per block by exact weight W=(k+1)DW = (k+1)^D, excludes conflicting pairs of block values by monotone clauses, and has, per assignment of the universal variables, the clause of the blocks with values that decide the XX-atoms of ψψ in a way making ψψ true for some assignment of the existential variables. It is computed in fixed-parameter time by an IMP+ program.