Theorem 3(a,b) — Polynomial-Time Binary Encoding Reductions from PARTITION to Two-Machine Scheduling
ProvedSchedComplexity.Partition.partition_twoMachine_encoding_reductioncomputational-complexitypartitionscheduling
Establishes the existence of polynomial-time computable functions on strings that map for positive integers to and instances in and corresponding to and .
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_Partition_PartitionProblem import Definitions.Def_SchedComplexity_Partition_Languages import Definitions.Def_SchedComplexity_Partition_Constructions
Formal statement
namespace SchedComplexity.Partition
open ProjSchedTW.Complexity (BSym encNats)
/-- Polynomial-time binary encoding reductions for Theorem 3(a) and 3(b) (Brucker, Lenstra &
Rinnooy Kan 1975, p. 15): maps `encNats a` (for positive integers `a`) to `cmaxCode` and
`sumWCCode` instances in `cmaxLang` and `sumWCLang` corresponding to `procA a`, `yA a` and
`procB a`, `yB a`. -/
theorem partition_twoMachine_encoding_reduction :
(∃ fA : List BSym → List BSym, CookPvsNP.PolyTimeComputable fA ∧
∀ c : List BSym,
(∃ a : List ℕ, (∀ x ∈ a, 0 < x) ∧
(∃ σ : Schedule a.length, σ.IsFeasible (procA a) ∧
∀ j, (σ.completion (procA a) j : ℝ) ≤ yA a) ∧
c = encNats a) ↔ fA c ∈ cmaxLang) ∧
(∃ fB : List BSym → List BSym, CookPvsNP.PolyTimeComputable fB ∧
∀ c : List BSym,
(∃ a : List ℕ, (∀ x ∈ a, 0 < x) ∧
(∃ σ : Schedule a.length, σ.IsFeasible (procB a) ∧
(σ.sumWC (procB a) (procB a) : ℝ) ≤ yB a) ∧
c = encNats a) ↔ fB c ∈ sumWCLang) := by sorry
end SchedComplexity.PartitionSource
Brucker, Lenstra & Rinnooy Kan 1975, Complexity of Machine Scheduling Problems, Report BW 43/75, p. 15, Theorem 3(a,b)