Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Dual-rail Horn MaxSAT correctness, exact threshold and score cap

Proved
HornMaxSAT.DualRail.semantic_correctness

by kmehltretter82 · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorylogic

Let FFF be any finite CNF formula with NNN declared variables, and let (H,S,N)=HEnc⁡(F)(H,S,N)=\operatorname{HEnc}(F)(H,S,N)=HEnc(F) be the specified dual-rail partial MaxSAT instance from §5.2. Assignments bbb range over all 2N2N2N rail variables, hard feasibility means satisfying every clause of HHH, and score⁡S(b)\operatorname{score}_{S}(b)scoreS​(b) counts satisfied soft-clause occurrences with unit weight.

  1. Every clause of HHH and SSS is Horn.
  2. The exact decision threshold is NNN:
F is satisfiable⟺∃b  (b⊨H ∧ score⁡S(b)≥N).F\text{ is satisfiable}\quad\Longleftrightarrow\quad \exists b\;\bigl(b\models H\ \land\ \operatorname{score}_{S}(b)\ge N\bigr).F is satisfiable⟺∃b(b⊨H ∧ scoreS​(b)≥N).
  1. Every feasible assignment obeys the universal cap
∀b,b⊨H ⟹ score⁡S(b)≤N.\forall b,\quad b\models H\ \Longrightarrow\ \operatorname{score}_{S}(b)\le N.∀b,b⊨H ⟹ scoreS​(b)≤N.

The statement applies without a feasibility assumption, including N=0N=0N=0, empty clauses, duplicate clauses or literals, tautologies, contradictory units, and unused declared variables. Hornness counts distinct positive literals. This is the semantic correctness component of the paper's specific SAT-to-Horn-MaxSAT transformation and can be reused independently of its machine implementation.

Formalization Note. This is the exact semantic conjunct of the mission's existing root statement. All published definitions, the dual-rail clauses and the threshold are unchanged.

Preamble
import Definitions.Def_HornMaxSAT_DualRail_HEnc

set_option autoImplicit false
open WordRAM.Conjectures
open HornMaxSAT.DualRail
Formal statement
theorem HornMaxSAT.DualRail.semantic_correctness : ∀ F : SATInstance,
    (HEnc F).IsHorn ∧
    (F.Satisfiable ↔ ∃ b : Fin (HEnc F).numVars → Bool,
      (HEnc F).Feasible b ∧ F.variables ≤ (HEnc F).score b) ∧
    (∀ b : Fin (HEnc F).numVars → Bool,
      (HEnc F).Feasible b → (HEnc F).score b ≤ F.variables) := by sorry
Source
Marques-Silva, Ignatiev and Morgado, Horn Maximum Satisfiability: Reductions, Algorithms and Applications, arXiv:1705.05335v1, §5.2, p. 8 (PDF p. 8), unnumbered HEnc correctness claim; polynomial reducibility context §1, p. 1 and §2, p. 3; https://arxiv.org/abs/1705.05335v1. This is an exact conjunct of the existing mission root HornMaxSAT.DualRail.sat_to_horn_maxsat (614d913b-e63d-4b87-a5eb-7f78cb3ebd7e).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me