Theorem 4(a) — Polynomial-Time Multiplicity-Encoding Reduction from KNAPSACK to
ProvedSchedComplexity.TotalCompletion.knapsack_mult_encoding_reductioncomputational-complexityknapsackscheduling
There exists a polynomial-time computable function on strings that maps binary-coded KNAPSACK instances with to multiplicity-encoded instances in representing , 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_CookPvsNP_defs import Definitions.Def_SchedComplexity_TotalCompletion_Knapsack import Definitions.Def_SchedComplexity_TotalCompletion_SingleMachine import Definitions.Def_SchedComplexity_TotalCompletion_Construction
Formal statement
namespace SchedComplexity.TotalCompletion
open ProjSchedTW.Complexity (BSym encNats)
/-- Polynomial-time multiplicity-encoding reduction for Theorem 4(a) (Brucker, Lenstra &
Rinnooy Kan 1975, pp. 22–23, Remark p. 23): there is a polynomial-time computable function `f` on
`BSym` strings that maps binary-coded KNAPSACK instances `knapsackCode a b` with `0 < b < sumA a`
to multiplicity-encoded instances in `sumCLangMult` representing `(procTime a b, weight a b,
release a b, yThreshold a b)`, and handles boundary instances `b ≥ sumA a`. -/
theorem knapsack_mult_encoding_reduction :
∃ f : List BSym → List BSym, CookPvsNP.PolyTimeComputable f ∧
∀ x : List BSym,
((∃ (t : ℕ) (a : Fin t → ℕ) (b : ℕ),
IsKnapsackInstance a b ∧ b < sumA a ∧
IsYes (procTime a b) (weight a b) (release a b) (yThreshold a b) ∧
x = knapsackCode a b) ∨
(∃ (t : ℕ) (a : Fin t → ℕ) (b : ℕ),
IsKnapsackInstance a b ∧ b = sumA a ∧ x = knapsackCode a b)) ↔
f x ∈ sumCLangMult := by sorry
end SchedComplexity.TotalCompletionSource
Brucker, Lenstra & Rinnooy Kan 1975, Complexity of Machine Scheduling Problems, Report BW 43/75, pp. 22–23, Theorem 4(a) and Remark