Theorem 4(d) — Polynomial-Time Multiplicity-Encoding Reduction from KNAPSACK to
ProvedSchedComplexity.Tardiness.knapsack_wt_encoding_reductioncomputational-complexityknapsackscheduling
There exists a polynomial-time computable function on strings that maps binary-coded KNAPSACK instances with to multiplicity-encoded instances in with parameter , and resolves boundary instances .
Preamble
import Mathlib.Data.Real.Basic import Mathlib.Data.Rat.Defs import Mathlib.Data.Nat.Bits import Mathlib.Data.Fintype.Basic import Mathlib.Data.Fintype.Sum import Mathlib.Data.Finset.Max import Mathlib.Data.Finset.Sort import Mathlib.Data.Finset.Lattice.Fold import Mathlib.Data.Set.Card import Mathlib.Data.List.Sort import Mathlib.Logic.Equiv.Fin.Rotate import Mathlib.Combinatorics.SimpleGraph.Basic import Mathlib.Tactic import Definitions.Def_SchedComplexity_Tardiness_Knapsack import Definitions.Def_SchedComplexity_Tardiness_MultLang import Definitions.Def_SchedComplexity_Tardiness_Construction
Formal statement
namespace SchedComplexity.Tardiness
open CookPvsNP ProjSchedTW.Complexity
/-- Polynomial-time multiplicity-encoding reduction for Theorem 4(d) (Brucker, Lenstra &
Rinnooy Kan 1975, pp. 20–21, Remark p. 23): there is a polynomial-time computable function `f` on
`BSym` strings that maps binary-coded KNAPSACK instances `encNats (b :: List.ofFn a)` with
`0 < b < bigA a` to multiplicity-encoded instances in `wtLangMult` with parameter
`τ = 2 * tPrime a b + bigA a + 1`, and handles boundary instances `b ≥ bigA a`. -/
theorem knapsack_wt_encoding_reduction :
∃ f : List BSym → List BSym, PolyTimeComputable f ∧
∀ x : List BSym,
((∃ (t : ℕ) (a : Fin t → ℕ) (b : ℕ),
(∀ j, 0 < a j) ∧ 0 < b ∧ b < bigA a ∧
HasScheduleLE (wtP a b (2 * tPrime a b + bigA a + 1))
(wtW a b (2 * tPrime a b + bigA a + 1))
(wtD a b (2 * tPrime a b + bigA a + 1))
(yThr a b (2 * tPrime a b + bigA a + 1)) ∧
x = encNats (b :: List.ofFn a)) ∨
(∃ (t : ℕ) (a : Fin t → ℕ) (b : ℕ),
(∀ j, 0 < a j) ∧ 0 < b ∧ b = bigA a ∧ x = encNats (b :: List.ofFn a))) ↔
f x ∈ wtLangMult := by sorry
end SchedComplexity.TardinessSource
Brucker, Lenstra & Rinnooy Kan 1975, Complexity of Machine Scheduling Problems, Report BW 43/75, pp. 20–21, 23, Theorem 4(d) and Remark