Polynomial-Time Reduction from Even-Odd Partition to Total Discrepancy
ProvedGTWSched.NPC.evenOdd_polyReducible_tdThe Even-Odd Partition language () is polynomial-time many-one reducible to the Total Discrepancy scheduling language () via the -task instance of Theorem 1 (Garey, Tarjan & Wilfong 1988, pp. 336–337).
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 evenOdd_polyReducible_td :
PolyReducible evenOddLang tdLang := by sorry
end GTWSched.NPCSource
Garey, Tarjan & Wilfong (1988), One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Operations Research 36(2), Theorem 1, pp. 336–337