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

Lax496464.WH_D07_DefinabilityToWSat · concepts/Lax496464/WH_D07_DefinabilityToWSat.lean · lax-496464

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    For every Π1\Pi_1-sentence φ(X)\varphi(X) there is a d≥1d \ge 1 such that p-WDφ≤fptp-WSat(d-CNF)p\text{-WD}_\varphi \le^{\mathrm{fpt}} p\text{-WSat}(d\text{-CNF}) [FG06, Lemma 6.37]. Together with WHD08WSatInA1WH_D08_WSatInA1 this gives W[1]⊆A[1]\mathrm{W}[1] \subseteq \mathrm{A}[1].

    Construction. Write the quantifier-free part of φ=∀x1…∀xr ψ\varphi = \forall x_1 \dots \forall x_r\, \psi in conjunctive normal form ⋀i∈I⋁j∈Jλij\bigwedge_{i \in I} \bigvee_{j \in J} \lambda_{ij}. Let UU be the elements occurring in the structure's word together with the first ∣x∣+s⋅k+r|x| + s\cdot k + r elements; the remaining elements occur in no relation and are interchangeable, so a witness can be moved into UU. Take a propositional variable YaˉY_{\bar a} for every aˉ∈Us\bar a \in U^s (ss the arity of XX), meaning aˉ∈X\bar a \in X. For every i∈Ii \in I and a1,…,ar∈Ua_1, \dots, a_r \in U form the clause of the literals λij(a1,…,ar)\lambda_{ij}(a_1, \dots, a_r): a literal (¬)Xyˉ(\neg) X\bar y becomes (¬)Yaˉ(\neg) Y_{\bar a} for the tuple aˉ\bar a of values of yˉ\bar y; a literal without XX is evaluated in A\mathcal A and dropped if false, and the whole clause is dropped if it is true. The clauses Yaˉ∨¬YaˉY_{\bar a} \vee \neg Y_{\bar a} make every variable occur. Then A⊨φ(S)\mathcal A \models \varphi(S) iff {Ybˉ:bˉ∈S}\{Y_{\bar b} : \bar b \in S\} satisfies the formula, and kk is unchanged.

    Complexity. The formula has O(∣U∣r+s⋅∣φ∣)O(|U|^{r+s}\cdot|\varphi|) literals; since ∣U∣|U| grows with kk, the reduction runs in time (∣x∣⋅k)O(1)(|x|\cdot k)^{O(1)}, fixed-parameter.

    Concept map
    14 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax496464.WH_B3_LogicProblems
    2import Lax496464.WH_A2_FptReductions
    3import Lax496464.WH_C3_WeightedSat
    4
    5/-!
    6---
    7title: Weighted Definability of a Π₁ Sentence Reduces to Weighted d-CNF Satisfiability
    8type: theorem
    9---
    10For every Π1\Pi_1-sentence φ(X)\varphi(X) there is a d≥1d \ge 1 such that
    11p-WDφ≤fptp-WSat(d-CNF)p\text{-WD}_\varphi \le^{\mathrm{fpt}} p\text{-WSat}(d\text{-CNF}) [FG06, Lemma 6.37]. Together with
    12`WH_D08_WSatInA1` this gives W[1]⊆A[1]\mathrm{W}[1] \subseteq \mathrm{A}[1].
    13
    14**Construction.** Write the quantifier-free part of φ=∀x1…∀xr ψ\varphi = \forall x_1 \dots \forall x_r\, \psi
    15in conjunctive normal form ⋀i∈I⋁j∈Jλij\bigwedge_{i \in I} \bigvee_{j \in J} \lambda_{ij}. Let UU be the
    16elements occurring in the structure's word together with the first ∣x∣+s⋅k+r|x| + s\cdot k + r elements;
    17the remaining elements occur in no relation and are interchangeable, so a witness can be moved into
    18UU. Take a propositional variable YaˉY_{\bar a} for every aˉ∈Us\bar a \in U^s (ss the arity of XX),
    19meaning aˉ∈X\bar a \in X. For every i∈Ii \in I and a1,…,ar∈Ua_1, \dots, a_r \in U form the clause of the
    20literals λij(a1,…,ar)\lambda_{ij}(a_1, \dots, a_r): a literal (¬)Xyˉ(\neg) X\bar y becomes (¬)Yaˉ(\neg) Y_{\bar a} for
    21the tuple aˉ\bar a of values of yˉ\bar y; a literal without XX is evaluated in A\mathcal A and
    22dropped if false, and the whole clause is dropped if it is true. The clauses
    23Yaˉ∨¬YaˉY_{\bar a} \vee \neg Y_{\bar a} make every variable occur. Then A⊨φ(S)\mathcal A \models \varphi(S) iff
    24{Ybˉ:bˉ∈S}\{Y_{\bar b} : \bar b \in S\} satisfies the formula, and kk is unchanged.
    25
    26**Complexity.** The formula has O(∣U∣r+s⋅∣φ∣)O(|U|^{r+s}\cdot|\varphi|) literals; since ∣U∣|U| grows with kk,
    27the reduction runs in time (∣x∣⋅k)O(1)(|x|\cdot k)^{O(1)}, fixed-parameter.
    28-/
    29
    30namespace Lax496464.WH_D07_DefinabilityToWSat
    31
    32open Lax496464.WH_B2_FirstOrder Lax496464.WH_B3_LogicProblems Lax496464.WH_A2_FptReductions
    33open Lax496464.WH_C3_WeightedSat
    34
    35/-- **`p-WD_φ ≤fpt p-WSat(d-CNF)`** for every `Π_1`-sentence `φ` and some `d`
    36[FG06, Lemma 6.37]. -/
    37axiom pWD_le_pWSat {φ : Formula} (s : ℕ) (hφ : IsPi 1 φ) (hs : IsSentence φ) :
    38 ∃ d, pWD φ s ≤ᶠᵖᵗ pWSat {α | IsDCNF d α}
    39
    40end Lax496464.WH_D07_DefinabilityToWSat
    41
    Show Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…