Lemma 3, pp. 10–11 — accurate order-polytope volume yields the linear-extension count
ProvedSPHardness.OrderPolytope.lemma_3counting-reductionlinear-extensionsorder-polytopep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite poset with , volume , and linear-extension count . If approximates with absolute error at most , where , then
Therefore is the unique integer nearest to . This is the rounding step of the reduction from #LinearExtension to order-polytope volume approximation.
Formalization Note The theorem records reduction correctness; it does not formalize #P-hardness or the polynomial-time cost of the remaining steps. The strict accuracy threshold rules out rounding ties.
Preamble
import Mathlib import Definitions.Def_SPHardness_OrderPolytope_Model
Formal statement
namespace SPHardness.OrderPolytope
open scoped Nat
/-- The rounding step in Lemma 3. -/
theorem lemma_3 (P : Type) [Fintype P] [PartialOrder P]
(ϑ ε : ℝ) (hε0 : 0 ≤ ε)
(hε : ε < 1 / (2 * ((Fintype.card P)! : ℝ)))
(hϑ : |ϑ - volOrder P| ≤ ε) :
|((Fintype.card P)! : ℝ) * ϑ - numLinExt P| < 1 / 2 := by sorry
end SPHardness.OrderPolytope
Source
Hanasusanto, Kuhn & Wiesemann, A comment on "computational complexity of stochastic programming problems", Optimization Online preprint 2015/03/4825 (version of October 6, 2015), pp. 10–11, Lemma 3 and its proof. https://optimization-online.org/wp-content/uploads/2015/03/4825.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.