P=NP 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 variable appearances. Döcker (2019) established that Monotone 3-SAT- (2, 2) is NP-complete via enforcer gadgets S (l₁, l₂, l₃). In this paper, we observe that Naïve orderings of variables can destroy the unimodal structure of the total satisfaction function S (k), as demonstrated by an explicit counterexample. We resolve this by introducing the canonical net-score ordering ^*, which sorts variables by their net positive contribution deg^+ (xᵢ) - deg^- (xᵢ) in decreasing order. We prove that under this ordering, the marginal gains from positive clauses are front-loaded while the marginal losses from negative clauses are back-loaded, ensuring that S (k) is unimodal (quasi-concave). This permits a binary search procedure that locates the maximum of S (k) in O (n) evaluation steps, each costing O (m), for a total complexity of O (m n). Combined with the threshold completeness lemma---which guarantees that every satisfying assignment can be realized as a threshold assignment under a suitable ordering---this yields a deterministic polynomial-time algorithm for Monotone SAT. Since Monotone 3-SAT- (2, 2) is NP-complete, this implies P = NP.