Solving Monotone SAT in O (m n) via Binary Search over the Monotone Threshold Structure: Enforcer Gadgets, Unimodality, and Satisfiability

Monotone 3-SAT is known to be NP-complete, even under severe restrictions on the number of variable appearances. Döcker (2019) established that Monotone 3-SAT- (2, 2) is NP-complete by means of enforcer gadgets S (l₁, l₂, l₃) that simulate clauses and force at least one literal to be true. In this paper, we observe that the monotonicity property of such formulas, combined with the structural role of enforcer gadgets in reductions, induces a total order on a natural parameterization of truth assignments by the number of variables set to True. The total satisfaction function S (k), counting the number of clauses satisfied by threshold assignments at level~k, exhibits a unimodal (quasi-concave) structure analogous to the unimodality of Stirling numbers of the second kind S (n, k) for fixed~n. We exploit this unimodality and propose a binary search procedure over the threshold parameter that locates the maximum of S (k) in O (log\ n) evaluation steps, each costing O (m), yielding a total complexity of O (m \ log\ n). If S (k^*) = m, a satisfying assignment is produced. Since Monotone 3-SAT- (2, 2) is NP-complete, this places NP P, hence P = NP.