Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Total discrepancy checker: polynomial-time cost filter

Proved
GTWSched.NPC.tdCheck_cost_filter

by tianyipeng · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexitynp-completenessschedulingturing-machines

Inputs of the checker are strings over the alphabet Σ={⊥}∪BSym⊔BSym\Sigma=\{\bot\}\cup\mathrm{BSym}\sqcup\mathrm{BSym}Σ={⊥}∪BSym⊔BSym of the form

u=enc(c) ⊥ enc(d),u=\mathrm{enc}(c)\,\bot\,\mathrm{enc}(d),u=enc(c)⊥enc(d),

where c=(c0,c1,… )c=(c_0,c_1,\dots)c=(c0​,c1​,…) is a list of integers written in binary (the instance part, tagged on the left) and d=(d0,d1,… )d=(d_0,d_1,\dots)d=(d0​,d1​,…) is a list of natural numbers written in binary (the certificate part, tagged on the right). For a total discrepancy instance the instance part is c=(N,k,M1,…,MN,l1,…,lN)c=(N,k,M_1,\dots,M_N,l_1,\dots,l_N)c=(N,k,M1​,…,MN​,l1​,…,lN​).

Let N=⌊∣d∣/3⌋N=\lfloor |d|/3\rfloorN=⌊∣d∣/3⌋ and read the certificate as d=(P0′,t1,h1,P1,…,tN,hN,PN)d=(P_{0}',t_1,h_1,P_1,\dots,t_N,h_N,P_N)d=(P0′​,t1​,h1​,P1​,…,tN​,hN​,PN​), i.e. ti=d3i−2t_i=d_{3i-2}ti​=d3i−2​, hi=d3i−1h_i=d_{3i-1}hi​=d3i−1​, Pi=d3iP_i=d_{3i}Pi​=d3i​ for 1≤i≤N1\le i\le N1≤i≤N and P0′=d0P_0'=d_0P0′​=d0​; write Pi−1′=d3i−3P_{i-1}'=d_{3i-3}Pi−1′​=d3i−3​ for the entry preceding tit_iti​. Put Mi=∣c1+i∣M_i=|c_{1+i}|Mi​=∣c1+i​∣, li=∣c1+N+i∣l_i=|c_{1+N+i}|li​=∣c1+N+i​∣ and k=∣c1∣k=|c_1|k=∣c1​∣. The cost conditions are

d0=0,ti+li=hi,hi+Pi−1′≤2Mi+Pi,2Mi+Pi−1′≤hi+Pi(1≤i≤N),d3N≤2k.d_0=0,\qquad t_i+l_i=h_i,\qquad h_i+P_{i-1}'\le 2M_i+P_i,\qquad 2M_i+P_{i-1}'\le h_i+P_i\quad(1\le i\le N),\qquad d_{3N}\le 2k .d0​=0,ti​+li​=hi​,hi​+Pi−1′​≤2Mi​+Pi​,2Mi​+Pi−1′​≤hi​+Pi​(1≤i≤N),d3N​≤2k.

(Equivalently Pi−Pi−1′≥∣hi−2Mi∣P_i-P'_{i-1}\ge|h_i-2M_i|Pi​−Pi−1′​≥∣hi​−2Mi​∣, so the entries PPP certify ∑i∣hi−2Mi∣≤2k\sum_i|h_i-2M_i|\le 2k∑i​∣hi​−2Mi​∣≤2k.) There is a structured multi-stack program running in at most ∣u∣K+K|u|^K+K∣u∣K+K steps that outputs the empty string on every input u=enc(c) ⊥ enc(d)u=\mathrm{enc}(c)\,\bot\,\mathrm{enc}(d)u=enc(c)⊥enc(d) violating one of these conditions, and outputs uuu unchanged on every other input (including inputs not of this form).

Here tit_iti​ is a doubled starting time and hi=ti+lih_i=t_i+l_ihi​=ti​+li​ the doubled midtime of task iii, so the conditions say that the schedule with starting times ti/2t_i/2ti​/2 has total discrepancy ∑i∣hi/2−Mi∣≤k\sum_i|h_i/2-M_i|\le k∑i​∣hi​/2−Mi​∣≤k; this is the cost check of the certificate checker for the total discrepancy problem.

Formalization Note Indices in Lean are 0-based: task i∈{0,…,N−1}i\in\{0,\dots,N-1\}i∈{0,…,N−1} uses d3i,d3i+1,d3i+2,d3i+3d_{3i},d_{3i+1},d_{3i+2},d_{3i+3}d3i​,d3i+1​,d3i+2​,d3i+3​ and c2+ic_{2+i}c2+i​, c2+N+ic_{2+N+i}c2+N+i​. Absolute values natAbs of the instance entries are used so that the statement makes sense for every integer list; for well-formed instances these entries are positive.

Preamble
import Mathlib
import Definitions.Def_CookPvsNP_StackProgram
import Definitions.Def_ProjSchedTW_Complexity_Encoding

open CookPvsNP
Formal statement
namespace GTWSched.NPC

open ProjSchedTW.Complexity

/-- Cost filter of the total-discrepancy certificate checker. With `N = |d| / 3`, the certificate
`d = P₋₁, t₁, h₁, P₁, …, t_N, h_N, P_N` lists doubled starting times `tᵢ`, doubled midtimes
`hᵢ = tᵢ + lᵢ` and partial bounds `Pᵢ` with `Pᵢ - Pᵢ₋₁ ≥ |hᵢ - 2Mᵢ|`, `P₋₁ = 0` and
`P_N ≤ 2k`. A polynomial-time stack program erases exactly the inputs `enc(c) ⊥ enc(d)` violating
one of these conditions and keeps every other input. -/
theorem tdCheck_cost_filter : ∃ (K : Type) (_ : Fintype K) (_ : DecidableEq K)
    (p : StackProg K (Option (BSym ⊕ BSym))) (ki ko : K) (k : ℕ), ∀ u,
    ∃ s n, n ≤ u.length ^ k + k ∧ p.Exec (fun j => if j = ki then u else []) s n ∧
      ((∃ (c : List ℤ) (d : List ℕ),
          u = (encInts c).map (some ∘ Sum.inl) ++ none :: (encNats d).map (some ∘ Sum.inr) ∧
          ¬(d.getD 0 0 = 0 ∧
            (∀ i < d.length / 3,
              d.getD (3 * i + 1) 0 + (c.getD (2 + d.length / 3 + i) 0).natAbs =
                d.getD (3 * i + 2) 0 ∧
              d.getD (3 * i + 2) 0 + d.getD (3 * i) 0 ≤
                2 * (c.getD (2 + i) 0).natAbs + d.getD (3 * i + 3) 0 ∧
              2 * (c.getD (2 + i) 0).natAbs + d.getD (3 * i) 0 ≤
                d.getD (3 * i + 2) 0 + d.getD (3 * i + 3) 0) ∧
            d.getD (3 * (d.length / 3)) 0 ≤ 2 * (c.getD 1 0).natAbs)) → s ko = []) ∧
      (¬(∃ (c : List ℤ) (d : List ℕ),
          u = (encInts c).map (some ∘ Sum.inl) ++ none :: (encNats d).map (some ∘ Sum.inr) ∧
          ¬(d.getD 0 0 = 0 ∧
            (∀ i < d.length / 3,
              d.getD (3 * i + 1) 0 + (c.getD (2 + d.length / 3 + i) 0).natAbs =
                d.getD (3 * i + 2) 0 ∧
              d.getD (3 * i + 2) 0 + d.getD (3 * i) 0 ≤
                2 * (c.getD (2 + i) 0).natAbs + d.getD (3 * i + 3) 0 ∧
              2 * (c.getD (2 + i) 0).natAbs + d.getD (3 * i) 0 ≤
                d.getD (3 * i + 2) 0 + d.getD (3 * i + 3) 0) ∧
            d.getD (3 * (d.length / 3)) 0 ≤ 2 * (c.getD 1 0).natAbs)) → s ko = u) := 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 (membership of the total discrepancy problem in NP, left there "as a simple exercise"); technical lemma of the polynomial-time certificate checker used in the proof of GTWSched.NPC.td_mem_NP

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me