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.
Description
for every -sentence φ = ∀ x̄ ∃ ȳ ψ (Flum–Grohe,
Theorem 7.1(1) for , via Lemma 7.2 and the Propositional Normalization Lemma 7.5). The
monotone formula has a variable for every block of slots with values ( fixed by ), forces
one value per block by exact weight , 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 -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.