Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Total discrepancy checker: polynomial-time length filter

Proved
GTWSched.NPC.tdCheck_len_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​).

There is a structured multi-stack program (hence, by stack_program_polytime, a polynomial-time Turing machine) whose number of steps on an input uuu is at most ∣u∣K+K|u|^K+K∣u∣K+K for a constant KKK, and which outputs uuu itself if

  1. u=enc(c) ⊥ enc(d)u=\mathrm{enc}(c)\,\bot\,\mathrm{enc}(d)u=enc(c)⊥enc(d) for some integer list ccc and natural-number list ddd,
  2. every entry of ccc is positive,
  3. ∣c∣=2+2c0|c| = 2+2c_0∣c∣=2+2c0​, and
  4. ∣d∣=3c0+1|d| = 3c_0+1∣d∣=3c0​+1,

and outputs the empty string otherwise.

This is the shape check of the certificate checker for the total discrepancy problem: it accepts exactly the well-formed pairs (instance code, certificate code) whose instance part has the shape N,k,M1,…,MN,l1,…,lNN,k,M_1,\dots,M_N,l_1,\dots,l_NN,k,M1​,…,MN​,l1​,…,lN​ with positive entries and whose certificate has 3N+13N+13N+1 entries.

Formalization Note The program is a CookPvsNP.StackProg over the alphabet Option (BSym ⊕ BSym); the input sits on stack ki, the output is read from stack ko. The certificate list is written with encNats, the instance list with encInts.

Preamble
import Mathlib
import Definitions.Def_CookPvsNP_StackProgram
import Definitions.Def_ProjSchedTW_Complexity_Encoding

open CookPvsNP
Formal statement
namespace GTWSched.NPC

open ProjSchedTW.Complexity

/-- Length filter of the total-discrepancy certificate checker: a polynomial-time stack program
that keeps exactly the inputs `enc(c) ⊥ enc(d)` with positive entries `c = N, k, M₁, …, M_N,
l₁, …, l_N` (so `|c| = 2 + 2N`) and a certificate `d` of length `3N + 1`, and erases every other
input. -/
theorem tdCheck_len_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) ∧
          (∀ v ∈ c, 0 < v) ∧ c.length = 2 + 2 * (c.getD 0 0).toNat ∧
          d.length = 3 * (c.getD 0 0).toNat + 1) → s ko = u) ∧
      (¬(∃ (c : List ℤ) (d : List ℕ),
          u = (encInts c).map (some ∘ Sum.inl) ++ none :: (encNats d).map (some ∘ Sum.inr) ∧
          (∀ v ∈ c, 0 < v) ∧ c.length = 2 + 2 * (c.getD 0 0).toNat ∧
          d.length = 3 * (c.getD 0 0).toNat + 1) → s ko = []) := 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