Proof of Theorem 1, p. 125 — Problems 7 and 8 are equivalent
ProvedMurtyKabadi.Reduction.problems7_8_equivp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-programmingsubset-sum
Let , let be positive integers and an integer with . Then
On the constant and linear terms of are rewritten using , which turns into the quadratic form ; this makes the problem a question about a homogeneous quadratic on the simplex-like set .
Formalization Note The hypothesis is the paper's tacit assumption. At the statement is false in Lean: , there, while because every sum is empty and .
Preamble
import Mathlib import Definitions.Def_MurtyKabadi_Reduction_Construction
Formal statement
namespace MurtyKabadi.Reduction
theorem problems7_8_equiv {n : ℕ} (hn : 0 < n) (d : Fin n → ℕ) (d0 δ : ℕ)
(hd : ∀ j, 0 < d j) (hd0 : 0 < d0)
(hδ : 4 * (d0 * ∑ j, d j) ^ 2 * n ^ 3 < δ) :
(∃ p ∈ P n, f2 d d0 δ p.1 p.2 ≤ 0) ↔ ∃ p ∈ P n, f4 d d0 δ p.1 p.2 ≤ 0 := by sorry
end MurtyKabadi.Reduction
Source
Murty and Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Math. Programming 39 (1987), p. 125, proof of Theorem 1, second paragraph (Problems 7 and 8 are equivalent)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.