Total discrepancy checker: polynomial-time cost filter
ProvedGTWSched.NPC.tdCheck_cost_filterInputs of the checker are strings over the alphabet of the form
where is a list of integers written in binary (the instance part, tagged on the left) and 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 .
Let and read the certificate as , i.e. , , for and ; write for the entry preceding . Put , and . The cost conditions are
(Equivalently , so the entries certify .) There is a structured multi-stack program running in at most steps that outputs the empty string on every input violating one of these conditions, and outputs unchanged on every other input (including inputs not of this form).
Here is a doubled starting time and the doubled midtime of task , so the conditions say that the schedule with starting times has total discrepancy ; this is the cost check of the certificate checker for the total discrepancy problem.
Formalization Note Indices in Lean are 0-based: task uses and , . 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.
import Mathlib import Definitions.Def_CookPvsNP_StackProgram import Definitions.Def_ProjSchedTW_Complexity_Encoding open CookPvsNP
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