Weighted d-CNF Satisfiability Is in A[1]
Lax496464.WH_D08_WSatInA1 · concepts/Lax496464/WH_D08_WSatInA1.lean · lax-496464
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
For every , [FG06, Theorem 6.28]. Together with this gives .
Construction. Given -CNF and , the reduction builds a structure and a -sentence , with depending on and only, such that the sentence holds exactly when a set of variables satisfies [FG06, Lemma 6.31]. Each variable is represented by its first occurrence in . A clause is satisfied by the chosen set exactly when the set does not contain all of or meets . For each negative part, the positive parts form a hypergraph with edges of size at most ; its hitting sets of size at most are found by a search tree of 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 : fixed-parameter, not polynomial.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax496464.WH_B4_Hierarchies |
| 2 | import Lax496464.WH_C3_WeightedSat |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Weighted d-CNF Satisfiability Is in A[1] |
| 7 | type: theorem |
| 8 | --- |
| 9 | For every , [FG06, Theorem 6.28]. Together with |
| 10 | `WH_D07_DefinabilityToWSat` this gives . |
| 11 | |
| 12 | **Construction.** Given -CNF and , the reduction builds a structure and a |
| 13 | -sentence , |
| 14 | with depending on and only, such that the sentence holds exactly when a set of |
| 15 | variables satisfies [FG06, Lemma 6.31]. Each variable is represented by its first |
| 16 | occurrence in . A clause |
| 17 | is satisfied by the chosen set exactly when the set does not contain all of |
| 18 | or meets . For each negative part, the |
| 19 | positive parts form a hypergraph with edges of size at most ; its hitting sets of size at most |
| 20 | are found by a search tree of branches [FG06, Lemma 1.17], and the sets found are stored |
| 21 | in a relation, grouped by negative part. The sentence names the hitting set it uses by further |
| 22 | existentially quantified variables. |
| 23 | |
| 24 | **Complexity.** The reduction runs in time : |
| 25 | fixed-parameter, not polynomial. |
| 26 | -/ |
| 27 | |
| 28 | namespace Lax496464.WH_D08_WSatInA1 |
| 29 | |
| 30 | open Lax496464.WH_B4_Hierarchies Lax496464.WH_C3_WeightedSat |
| 31 | |
| 32 | /-- **`p-WSat(d-CNF) ∈ A[1]`** [FG06, Theorem 6.28]. -/ |
| 33 | axiom pWSat_mem_A1 (d : ℕ) : pWSat {α | IsDCNF d α} ∈ A 1 |
| 34 | |
| 35 | end Lax496464.WH_D08_WSatInA1 |
| 36 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments