Theorem 3, p. 11 — accurate expected recourse values recover the linear-extension count
ProvedSPHardness.OrderPolytope.theorem_3This states the correctness of the counting reduction underlying Theorem 3. Let be a finite poset with . Let be the expected optimal value of the random-recourse program (10) under the uniform law on , and let count its linear extensions. If approximates to absolute accuracy with , then
Thus is the unique nearest integer to . The result combines the pointwise value of (10), the expected-value/volume identity, and the factorial volume identity.
Formalization Note The original Theorem 3 asserts strong #P-hardness. This statement formalizes the mathematical correctness of its reduction, not a complexity class, polynomial-time computability, input bit lengths, or the unary-encoding argument. A general finite poset represents the paper's with its given partial order; is its cardinality, not an independent parameter.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_SPHardness_OrderPolytope_Model
namespace SPHardness.OrderPolytope
open scoped Nat
/-- Correctness of the counting reduction underlying Theorem 3. -/
theorem theorem_3 (P : Type) [Fintype P] [PartialOrder P]
(ϑ ε : ℝ) (hε0 : 0 ≤ ε)
(hε : ε < 1 / (2 * ((Fintype.card P)! : ℝ)))
(hϑ : |ϑ - expRecourse P| ≤ ε) :
|((Fintype.card P)! : ℝ) * (1 - ϑ) - numLinExt P| < 1 / 2 := by sorry
end SPHardness.OrderPolytope
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.