Polynomial-Time Reduction from Positive Partition to Even-Odd Partition
ProvedGTWSched.NPC.positivePartition_polyReducible_evenOddThe positive language () is polynomial-time many-one reducible to the Even-Odd Partition language () via the construction , , of Lemma 1 (Garey, Tarjan & Wilfong 1988, p. 333).
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 CookPvsNP ProjSchedTW.Complexity
theorem positivePartition_polyReducible_evenOdd :
PolyReducible positivePartitionLang evenOddLang := by sorry
end GTWSched.NPCSource
Garey, Tarjan & Wilfong (1988), One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Operations Research 36(2), Lemma 1, p. 333