Weighted Definability of a Π₁ Sentence Reduces to Weighted d-CNF Satisfiability
Lax496464.WH_D07_DefinabilityToWSat · concepts/Lax496464/WH_D07_DefinabilityToWSat.lean · lax-496464
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
For every -sentence there is a such that [FG06, Lemma 6.37]. Together with this gives .
Construction. Write the quantifier-free part of in conjunctive normal form . Let be the elements occurring in the structure's word together with the first elements; the remaining elements occur in no relation and are interchangeable, so a witness can be moved into . Take a propositional variable for every ( the arity of ), meaning . For every and form the clause of the literals : a literal becomes for the tuple of values of ; a literal without is evaluated in and dropped if false, and the whole clause is dropped if it is true. The clauses make every variable occur. Then iff satisfies the formula, and is unchanged.
Complexity. The formula has literals; since grows with , the reduction runs in time , fixed-parameter.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax496464.WH_B3_LogicProblems |
| 2 | import Lax496464.WH_A2_FptReductions |
| 3 | import Lax496464.WH_C3_WeightedSat |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Weighted Definability of a Π₁ Sentence Reduces to Weighted d-CNF Satisfiability |
| 8 | type: theorem |
| 9 | --- |
| 10 | For every -sentence there is a such that |
| 11 | [FG06, Lemma 6.37]. Together with |
| 12 | `WH_D08_WSatInA1` this gives . |
| 13 | |
| 14 | **Construction.** Write the quantifier-free part of |
| 15 | in conjunctive normal form . Let be the |
| 16 | elements occurring in the structure's word together with the first elements; |
| 17 | the remaining elements occur in no relation and are interchangeable, so a witness can be moved into |
| 18 | . Take a propositional variable for every ( the arity of ), |
| 19 | meaning . For every and form the clause of the |
| 20 | literals : a literal becomes for |
| 21 | the tuple of values of ; a literal without is evaluated in and |
| 22 | dropped if false, and the whole clause is dropped if it is true. The clauses |
| 23 | make every variable occur. Then iff |
| 24 | satisfies the formula, and is unchanged. |
| 25 | |
| 26 | **Complexity.** The formula has literals; since grows with , |
| 27 | the reduction runs in time , fixed-parameter. |
| 28 | -/ |
| 29 | |
| 30 | namespace Lax496464.WH_D07_DefinabilityToWSat |
| 31 | |
| 32 | open Lax496464.WH_B2_FirstOrder Lax496464.WH_B3_LogicProblems Lax496464.WH_A2_FptReductions |
| 33 | open 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]. -/ |
| 37 | axiom pWD_le_pWSat {φ : Formula} (s : ℕ) (hφ : IsPi 1 φ) (hs : IsSentence φ) : |
| 38 | ∃ d, pWD φ s ≤ᶠᵖᵗ pWSat {α | IsDCNF d α} |
| 39 | |
| 40 | end Lax496464.WH_D07_DefinabilityToWSat |
| 41 |
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments