Proof of LEMMA 1, p. 333 — the instance EO built from a partition instance Y has a solution iff Y does
ProvedGTWSched.NPC.lemma_1_constructionnp-completenessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1partitionreduction
Let with and every be an instance of Partition. Define by
Then
- is an instance of even-odd partition (positive integers with for ), and
- can be split into two parts of equal sum if and only if can be split into two parts of equal sum containing exactly one of each, for every .
This is the reduction from Partition to even-odd partition in the proof of LEMMA 1.
Formalization Note is a list of natural numbers (y ≠ [] is ); the paper assumes "without loss of generality", and that assumption is a hypothesis here. Partition is the published ProjSchedTW.Complexity.PartitionYes, which splits the index set of the list.
Preamble
import Mathlib import Definitions.Def_CookPvsNP_defs import Definitions.Def_ProjSchedTW_Complexity_Encoding import Definitions.Def_GTWSched_NPC_Schedules import Definitions.Def_GTWSched_NPC_Problems
Formal statement
namespace GTWSched.NPC
open ProjSchedTW.Complexity
/-- Proof of LEMMA 1, p. 333: for a partition instance `Y = [y₁, …, yₙ]` with `n ≥ 1` and every
`yᵢ > 1`, the list `X` with `x₁ = 1`, `x₂ᵢ = x₂ᵢ₋₁ + yᵢ`, `x₂ᵢ₊₁ = x₂ᵢ + 1` is an even-odd
partition instance, and `Y` has a partition into two parts of equal sum iff `X` has an even-odd
partition into two parts of equal sum. -/
theorem lemma_1_construction (y : List ℕ) (hy : y ≠ []) (hy1 : ∀ v ∈ y, 1 < v) :
EOInstance (eoOfPartition y) ∧ (PartitionYes y ↔ EOYes (eoOfPartition y)) := by sorry
end GTWSched.NPC
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 333, proof of LEMMA 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.