Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The specified dual-rail encoder is uniformly polynomial-time

Proved
HornMaxSAT.DualRail.henc_polytime

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

complexity-theorycomputability

Let HEnc⁡\operatorname{HEnc}HEnc be the specified dual-rail transformation from finite CNF formulas to partial MaxSAT instances, including the exact threshold equal to the number of declared source variables. There exist one fixed deterministic finite-control multi-stack Turing machine and one polynomial p∈N[X]p\in\mathbb N[X]p∈N[X] such that, for every source formula FFF, the machine reads its published token encoding and halts with exactly the published encoding of HEnc⁡(F)\operatorname{HEnc}(F)HEnc(F) within

p(∣encodeSAT⁡(F)∣)p\bigl(|\operatorname{encodeSAT}(F)|\bigr)p(∣encodeSAT(F)∣)

actual machine steps.

The input and output alphabets are the published six-token alphabet. Declared-variable headers are unary; literal indices and the output threshold use terminated little-endian binary. The output includes the complete variable header, hard-clause collection, soft-clause collection, separators and threshold. One machine and one polynomial work uniformly for all finite source formulas, including zero declared variables, empty clauses, repeated literals, tautologies, contradictory units and unused declared variables. No satisfiability or target-feasibility assumption is imposed.

This is the computational component of the paper's explicit polynomial reduction, separated from its semantic correctness without altering the transformation or its encodings.

Formalization Note. The source gives a polynomial-time reduction in §§1–2 and §5.2; the fixed Mathlib multi-stack machine, the finite token encodings, and counting actual execution steps are the explicit conventions already selected by the existing mission root. The statement requires the exact final output configuration, rather than only an output-size bound or a high-level terminating function.

Preamble
import Definitions.Def_HornMaxSAT_DualRail_Serialization

set_option autoImplicit false
open HornMaxSAT.DualRail
Formal statement
theorem HornMaxSAT.DualRail.henc_polytime :
    Nonempty (Turing.TM2ComputableInPolyTime encodeSAT encodeMaxSAT HEnc) := 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