Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5.2 — SAT reduces to Horn MaxSAT by HEnc, with exact threshold NNN

Proved
HornMaxSAT.DualRail.sat_to_horn_maxsat

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

dual-railhorn-maxsatp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1polynomial-time-reductionsatisfiability

There is one deterministic finite-control multi-stack Turing machine and one polynomial with natural coefficients such that, for every finite CNF formula FFF, the machine transforms its specified finite-alphabet input code into the code of HEnc⁡(F)\operatorname{HEnc}(F)HEnc(F) within that polynomial in the input length. HEnc uses two rails per declared variable, the negative opposite-rail clause map, hard pair exclusions, and one positive soft unit clause per rail.

For every such formula FFF with NNN declared variables, write (H,S,N)=HEnc⁡(F)(H,S,N)=\operatorname{HEnc}(F)(H,S,N)=HEnc(F). Every clause in HHH and SSS is Horn, and

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)\geq N\bigr).F is satisfiable⟺∃b(b⊨H∧scoreS​(b)≥N).

Moreover,

∀b,b⊨H  ⟹  score⁡S(b)≤N.\forall b,\quad b\models H\;\Longrightarrow\;\operatorname{score}_S(b)\leq N.∀b,b⊨H⟹scoreS​(b)≤N.

Assignments are total on the 2N2N2N rails, feasibility means satisfying all hard clauses, and the score counts only satisfied soft clauses. The result includes arbitrary clause widths, zero variables, empty formulas, empty clauses, tautologies and contradictory formulas. No hard-feasible assignment is assumed to exist.

The theorem establishes correctness and efficiency of this particular reduction. It does not assert a polynomial-time solver for SAT or Horn MaxSAT. Its body is an open proof obligation.

Formalization Note Complexity is Mathlib's concrete TM2 step measure: one fixed finite-control machine and one polynomial precede the quantification over all inputs. Input and output use the six-token serializations with unary variable headers, binary literal indices and a binary output threshold. No explicit numerical running-time coefficient is claimed by the source or introduced here.

Differences from the source:

  • encoding: finite sets of one-based variables and clauses → zero-based Fin indices, list clause representations, and rails indexed 2i and 2i+1; reason: finite relabeling and repeated hard clauses or literals change no satisfaction or Hornness condition, and the generated soft list still contains exactly one unit clause per rail
  • encoding: polynomial-time reduction on explicitly listed variables → TM2ComputableInPolyTime for fixed six-token codes with unary variable headers, binary indices and a binary threshold; reason: this supplies a concrete uniform machine and input-length convention without changing the source instances or replacing runtime by output size
  • generalization: the variable universe is vars(F) → the declared finite universe may also contain unused variables; reason: setting the declared universe equal to vars(F) recovers every source instance with the same N and all four conclusion clauses
  • reading: the image of clause c_j has the same number of literals as c_i → HEnc maps each c_j literalwise to its own image; reason: the surrounding literal map uniquely fixes the intended index c_j, recorded as typo I1
Preamble
import Definitions.Def_HornMaxSAT_DualRail_Serialization

set_option autoImplicit false
Formal statement
namespace HornMaxSAT.DualRail

open WordRAM.Conjectures

/-- Section 5.2: the concrete HEnc is a uniform polynomial-time reduction,
with Horn output, exact decision threshold N, and universal feasible-score cap N. -/
theorem sat_to_horn_maxsat :
    Nonempty (Turing.TM2ComputableInPolyTime encodeSAT encodeMaxSAT HEnc) ∧
    ∀ 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

end HornMaxSAT.DualRail
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
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The statement is a conjunction of two parts. The first is a single computability claim. The second holds for every SAT instance FFF.

Notation. Several objects come from the imported module Definitions.Def_HornMaxSAT_DualRail_Serialization or the opened namespace WordRAM.Conjectures. Their definitions were not supplied with this declaration, so they are described here only by the role the statement gives them, not unfolded:

  • SATInstance\mathsf{SATInstance}SATInstance is a type of SAT instances.
  • For an instance FFF:
    • F.variablesF.\mathrm{variables}F.variables is a quantity attached to FFF, compared by ≤\le≤ with scores below.
    • "FFF is satisfiable" is a predicate on FFF.
  • H(F)H(F)H(F) (written HEnc F in the code) is a fixed function sending each SAT instance to an object of some MaxSAT-instance type. That object has:
    • a natural number of variables, nF=H(F).numVarsn_F = H(F).\mathrm{numVars}nF​=H(F).numVars;
    • a predicate "is Horn";
    • a feasibility predicate on assignments b:{0,…,nF−1}→{true,false}b : \{0,\dots,n_F-1\} \to \{\mathrm{true},\mathrm{false}\}b:{0,…,nF​−1}→{true,false};
    • a score function scoreH(F)(b)\mathrm{score}_{H(F)}(b)scoreH(F)​(b) on such assignments.
  • eSATe_{\mathrm{SAT}}eSAT​ (encodeSAT) and eMaxSATe_{\mathrm{MaxSAT}}eMaxSAT​ (encodeMaxSAT) are finite encodings. Each maps instances of its type to finite strings over a finite alphabet.

Part 1 (polynomial-time computability). There exists at least one witness of polynomial-time computability of HHH by a multi-stack (TM2) Turing machine, relative to the encodings eSATe_{\mathrm{SAT}}eSAT​ for inputs and eMaxSATe_{\mathrm{MaxSAT}}eMaxSAT​ for outputs. Concretely, there are:

  • one TM2 machine MMM;
  • one polynomial ppp with natural-number coefficients;

such that for every SAT instance FFF, MMM started on the string eSAT(F)e_{\mathrm{SAT}}(F)eSAT​(F) halts with output eMaxSAT(H(F))e_{\mathrm{MaxSAT}}(H(F))eMaxSAT​(H(F)) within p(∣eSAT(F)∣)p\big(|e_{\mathrm{SAT}}(F)|\big)p(∣eSAT​(F)∣) steps, where ∣⋅∣|\cdot|∣⋅∣ is string length. The same MMM and ppp serve all inputs. The claim concerns HHH only through these two encodings.

Part 2 (three properties of H(F)H(F)H(F)). For every SAT instance FFF, all three of the following hold.

  1. Horn. H(F)H(F)H(F) satisfies the "is Horn" predicate.
  2. Satisfiability equivalence. FFF is satisfiable if and only if some assignment bbb is both feasible for H(F)H(F)H(F) and scores at least F.variablesF.\mathrm{variables}F.variables:
F satisfiable  ⟺  ∃ b:{0,…,nF−1}→{true,false}   with   b feasible for H(F)   and   F.variables≤scoreH(F)(b).F \text{ satisfiable} \iff \exists\, b : \{0,\dots,n_F-1\}\to\{\mathrm{true},\mathrm{false}\} \;\text{ with }\; b \text{ feasible for } H(F) \;\text{ and }\; F.\mathrm{variables} \le \mathrm{score}_{H(F)}(b).F satisfiable⟺∃b:{0,…,nF​−1}→{true,false} with b feasible for H(F) and F.variables≤scoreH(F)​(b).

The inequality is non-strict (≥\ge≥, not >>>). 3. Score cap. Every feasible assignment scores at most F.variablesF.\mathrm{variables}F.variables:

∀ b:{0,…,nF−1}→{true,false},b feasible for H(F)  ⟹  scoreH(F)(b)≤F.variables.\forall\, b : \{0,\dots,n_F-1\}\to\{\mathrm{true},\mathrm{false}\},\quad b \text{ feasible for } H(F) \;\Longrightarrow\; \mathrm{score}_{H(F)}(b) \le F.\mathrm{variables}.∀b:{0,…,nF​−1}→{true,false},b feasible for H(F)⟹scoreH(F)​(b)≤F.variables.

Combining items 2 and 3, FFF is satisfiable exactly when some feasible assignment's score is ≥F.variables\ge F.\mathrm{variables}≥F.variables. If ≤\le≤ on the score type is antisymmetric (as on N\mathbb{N}N), this is the same as some feasible assignment's score being exactly F.variablesF.\mathrm{variables}F.variables. The code itself does not state "equal" or "maximum".

Degenerate cases.

  • Zero variables in H(F)H(F)H(F). If nF=0n_F = 0nF​=0, there is exactly one assignment, the empty one. Item 2 then says FFF is satisfiable iff that empty assignment is feasible and its score is ≥F.variables\ge F.\mathrm{variables}≥F.variables. Item 3 constrains only that one assignment.
  • No feasible assignments. If no assignment is feasible for H(F)H(F)H(F), item 3 holds vacuously, and item 2 forces FFF to be unsatisfiable.
  • F.variablesF.\mathrm{variables}F.variables is the least element. If F.variablesF.\mathrm{variables}F.variables is the least element of the score type (e.g. 000, should scores be natural numbers), two things follow. Item 2's threshold is met by every assignment, so it reduces to "FFF satisfiable iff some assignment is feasible for H(F)H(F)H(F)". Item 3 then forces every feasible assignment's score to equal that least element.
  • What cannot be stated. Whether an instance with no variables or no clauses exists, and what "satisfiable" means for it, depends on the unsupplied definitions of SATInstance\mathsf{SATInstance}SATInstance and Satisfiable\mathrm{Satisfiable}Satisfiable. Likewise, whether any total-function default values occur inside HHH, score\mathrm{score}score or Feasible\mathrm{Feasible}Feasible cannot be determined from the code given.
  • No hypotheses. The statement has none beyond the choice of FFF and bbb, so nothing in it is vacuous on its face.
  • Encoding dependence. Part 1 depends on the specific encodings eSATe_{\mathrm{SAT}}eSAT​ and eMaxSATe_{\mathrm{MaxSAT}}eMaxSAT​. Its strength therefore rests on how those encodings are defined, and that was not supplied.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

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