§5.2 — SAT reduces to Horn MaxSAT by HEnc, with exact threshold
ProvedHornMaxSAT.DualRail.sat_to_horn_maxsatThere is one deterministic finite-control multi-stack Turing machine and one polynomial with natural coefficients such that, for every finite CNF formula , the machine transforms its specified finite-alphabet input code into the code of 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 with declared variables, write . Every clause in and is Horn, and
Moreover,
Assignments are total on the 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
import Definitions.Def_HornMaxSAT_DualRail_Serialization set_option autoImplicit false
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
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 .
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:
- is a type of SAT instances.
- For an instance :
- is a quantity attached to , compared by with scores below.
- " is satisfiable" is a predicate on .
- (written
HEnc Fin 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, ;
- a predicate "is Horn";
- a feasibility predicate on assignments ;
- a score function on such assignments.
- (
encodeSAT) and (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 by a multi-stack (TM2) Turing machine, relative to the encodings for inputs and for outputs. Concretely, there are:
- one TM2 machine ;
- one polynomial with natural-number coefficients;
such that for every SAT instance , started on the string halts with output within steps, where is string length. The same and serve all inputs. The claim concerns only through these two encodings.
Part 2 (three properties of ). For every SAT instance , all three of the following hold.
- Horn. satisfies the "is Horn" predicate.
- Satisfiability equivalence. is satisfiable if and only if some assignment is both feasible for and scores at least :
The inequality is non-strict (, not ). 3. Score cap. Every feasible assignment scores at most :
Combining items 2 and 3, is satisfiable exactly when some feasible assignment's score is . If on the score type is antisymmetric (as on ), this is the same as some feasible assignment's score being exactly . The code itself does not state "equal" or "maximum".
Degenerate cases.
- Zero variables in . If , there is exactly one assignment, the empty one. Item 2 then says is satisfiable iff that empty assignment is feasible and its score is . Item 3 constrains only that one assignment.
- No feasible assignments. If no assignment is feasible for , item 3 holds vacuously, and item 2 forces to be unsatisfiable.
- is the least element. If is the least element of the score type (e.g. , should scores be natural numbers), two things follow. Item 2's threshold is met by every assignment, so it reduces to " satisfiable iff some assignment is feasible for ". 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 and . Likewise, whether any total-function default values occur inside , or cannot be determined from the code given.
- No hypotheses. The statement has none beyond the choice of and , so nothing in it is vacuous on its face.
- Encoding dependence. Part 1 depends on the specific encodings and . Its strength therefore rests on how those encodings are defined, and that was not supplied.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.