The specified dual-rail encoder is uniformly polynomial-time
ProvedHornMaxSAT.DualRail.henc_polytimeLet 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 such that, for every source formula , the machine reads its published token encoding and halts with exactly the published encoding of within
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.
import Definitions.Def_HornMaxSAT_DualRail_Serialization set_option autoImplicit false open HornMaxSAT.DualRail
theorem HornMaxSAT.DualRail.henc_polytime :
Nonempty (Turing.TM2ComputableInPolyTime encodeSAT encodeMaxSAT HEnc) := by sorry