Proof of `Weighted Definability of a Π₁ Sentence Reduces to Weighted d-CNF Satisfiability`

groundedproofs/Lax496464Proofs/WHierarchy/Lemmas/WDToWSat/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(d−CNF)p-WD_φ ≤fpt p-WSat(d-CNF) for every Π1Π_1-sentence φ=∀xsψφ = ∀ xs ψ (Flum–Grohe, Lemma 6.37), with d=2+(thetotallengthoftheclausesofaCNFofψ)d = 2 + (the total length of the clauses of a CNF of ψ). The formula has a variable for each ss-tuple of the elements UU (the elements 0,…,L−10, …, L-1, L=min(∣A∣,∣x∣+s⋅k+r)L = min(|A|, |x| + s·k + r), and every element occurring in a relation), a clause per assignment of elements of UU to the variables and clause of the CNF (its XX-literals, or Y0∨¬Y0Y₀ ∨ ¬Y₀ when a literal without XX holds), and the clauses Y∨¬YY ∨ ¬Y; kk stays kk. Elements outside UU are isolated and interchangeable, so a witness exists iff one exists within UU. The map is computed in fixed-parameter time by an IMP+ program.