§2.1, p. 336 — the total discrepancy problem is in NP
ProvedGTWSched.NPC.td_mem_NPcomplexitynp-completenessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
The total discrepancy problem belongs to NP: the language of codes of instances , for which some one-processor schedule with real starting times has is in
The paper leaves this "as a simple exercise".
Formalization Note NP is the published CookPvsNP.NP; the language is tdLang. A certificate cannot simply be a list of real starting times; a polynomial-size certificate exists because for a fixed task order the optimal starting times solve a linear program with integer data.
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 /-- p. 336: the total discrepancy problem is in NP. -/ theorem td_mem_NP : tdLang ∈ NP BSym := by sorry end GTWSched.NPC
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 336, §2.1, before THEOREM 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.