Weighted d-CNF Satisfiability Is in A[1]

Lax496464.WH_D08_WSatInA1 · concepts/Lax496464/WH_D08_WSatInA1.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 dd, p-WSat(d-CNF)∈A[1]p\text{-WSat}(d\text{-CNF}) \in \mathrm{A}[1] [FG06, Theorem 6.28]. Together with WHD07DefinabilityToWSatWH_D07_DefinabilityToWSat this gives W[1]⊆A[1]\mathrm{W}[1] \subseteq \mathrm{A}[1].

    Construction. Given α∈d\alpha \in d-CNF and kk, the reduction builds a structure and a Σ1\Sigma_1-sentence ∃x1…∃xk (⋀i<j¬ xi=xj∧ψ)\exists x_1 \dots \exists x_k\,(\bigwedge_{i<j} \neg\, x_i = x_j \wedge \psi), with ψ\psi depending on dd and kk only, such that the sentence holds exactly when a set of kk variables satisfies α\alpha [FG06, Lemma 6.31]. Each variable is represented by its first occurrence in α\alpha. A clause ¬Xi1∨⋯∨¬Xir∨Xj1∨⋯∨Xjs\neg X_{i_1} \vee \dots \vee \neg X_{i_r} \vee X_{j_1} \vee \dots \vee X_{j_s} is satisfied by the chosen set exactly when the set does not contain all of Xi1,…,XirX_{i_1}, \dots, X_{i_r} or meets {Xj1,…,Xjs}\{X_{j_1}, \dots, X_{j_s}\}. For each negative part, the positive parts form a hypergraph with edges of size at most dd; its hitting sets of size at most kk are found by a search tree of dkd^k branches [FG06, Lemma 1.17], and the sets found are stored in a relation, grouped by negative part. The sentence names the hitting set it uses by further existentially quantified variables.

    Complexity. The reduction runs in time (d+2)O(k)(k+2)O(d)⋅∣x∣O(1)(d+2)^{O(k)}(k+2)^{O(d)}\cdot|x|^{O(1)}: fixed-parameter, not polynomial.

    Concept map
    15 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_B4_Hierarchies
    2import Lax496464.WH_C3_WeightedSat
    3
    4/-!
    5---
    6title: Weighted d-CNF Satisfiability Is in A[1]
    7type: theorem
    8---
    9For every dd, p-WSat(d-CNF)∈A[1]p\text{-WSat}(d\text{-CNF}) \in \mathrm{A}[1] [FG06, Theorem 6.28]. Together with
    10`WH_D07_DefinabilityToWSat` this gives W[1]⊆A[1]\mathrm{W}[1] \subseteq \mathrm{A}[1].
    11
    12**Construction.** Given α∈d\alpha \in d-CNF and kk, the reduction builds a structure and a
    13Σ1\Sigma_1-sentence ∃x1…∃xk (⋀i<j¬ xi=xj∧ψ)\exists x_1 \dots \exists x_k\,(\bigwedge_{i<j} \neg\, x_i = x_j \wedge \psi),
    14with ψ\psi depending on dd and kk only, such that the sentence holds exactly when a set of kk
    15variables satisfies α\alpha [FG06, Lemma 6.31]. Each variable is represented by its first
    16occurrence in α\alpha. A clause ¬Xi1∨⋯∨¬Xir∨Xj1∨⋯∨Xjs\neg X_{i_1} \vee \dots \vee \neg X_{i_r} \vee X_{j_1} \vee \dots \vee X_{j_s}
    17 is satisfied by the chosen set exactly when the set does not contain all of
    18Xi1,…,XirX_{i_1}, \dots, X_{i_r} or meets {Xj1,…,Xjs}\{X_{j_1}, \dots, X_{j_s}\}. For each negative part, the
    19positive parts form a hypergraph with edges of size at most dd; its hitting sets of size at most
    20kk are found by a search tree of dkd^k branches [FG06, Lemma 1.17], and the sets found are stored
    21in a relation, grouped by negative part. The sentence names the hitting set it uses by further
    22existentially quantified variables.
    23
    24**Complexity.** The reduction runs in time (d+2)O(k)(k+2)O(d)⋅∣x∣O(1)(d+2)^{O(k)}(k+2)^{O(d)}\cdot|x|^{O(1)}:
    25fixed-parameter, not polynomial.
    26-/
    27
    28namespace Lax496464.WH_D08_WSatInA1
    29
    30open Lax496464.WH_B4_Hierarchies Lax496464.WH_C3_WeightedSat
    31
    32/-- **`p-WSat(d-CNF) ∈ A[1]`** [FG06, Theorem 6.28]. -/
    33axiom pWSat_mem_A1 (d : ℕ) : pWSat {α | IsDCNF d α} ∈ A 1
    34
    35end Lax496464.WH_D08_WSatInA1
    36
    Show Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…