Theorem 6, first sentence — the data of (HLP) remain integral with bit length
ProvedSelfDualLP.Complexity.theorem_6_databit-complexitycomplexitylinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , be integer data with and bit length . Under the choice (7) the additional data of (HLP),
are integral, and the bit length of all the (HLP) data ( and the right-hand side ) is : at most for an absolute constant .
This is why the complexity bound for (HLP) is stated in terms of the bit length of the original data.
Formalization Note Integrality is stated as: the real vectors and the real number obtained from the cast data are the casts of the corresponding integer expressions. is pinned with chosen before . The paper implicitly has ; this excludes an empty LP whose input length is zero while (HLP) still has a nonzero normalizing constant.
Preamble
import Mathlib import Definitions.Def_SelfDualLP_Complexity_HLP import Definitions.Def_SelfDualLP_Complexity_BitLength open Matrix
Formal statement
namespace SelfDualLP.Complexity
/-- Theorem 6, first sentence (p. 61). For integer data `(A, b, c)` with `n ≥ 1` and bit length `L`, the data
of (HLP) under (7) remain integral — `b̄ = b − Ae`, `c̄ = c − e`, `z̄ = cᵀe + 1` are the casts of
the integer vectors/number `bbarInt`, `cbarInt`, `zbarInt` — and the bit length of the (HLP)
data is `O(L)`: at most `C·L` for an absolute constant `C`. -/
theorem theorem_6_data :
∃ C : ℝ, 0 < C ∧ ∀ (m n : ℕ), 1 ≤ n →
∀ (A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ) (c : Fin n → ℤ),
bbar (castMat A) (castVec b) (ones n) = castVec (bbarInt A b) ∧
cbar (castMat A) (castVec c) 0 (ones n) = castVec (cbarInt c) ∧
zbar (castVec b) (castVec c) (ones n) 0 = ((zbarInt c : ℤ) : ℝ) ∧
(hlpBitLength A b c : ℝ) ≤ C * (bitLength A b c : ℝ) := by sorry
end SelfDualLP.Complexity
Source
Ye, Todd, Mizuno, An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm, Math. Oper. Res. 19(1) (1994), p. 61, Theorem 6 (first sentence); (8) on p. 58
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.