Total discrepancy checker: polynomial-time overlap filter
ProvedGTWSched.NPC.tdCheck_overlap_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 , let be the doubled starting time and the length of task (). The non-overlap condition is
There is a structured multi-stack program running in at most steps that outputs the empty string on every input violating this condition, and outputs unchanged on every other input (including inputs not of this form).
With starting times the condition says that the execution intervals of distinct tasks overlap at most in an endpoint, i.e. the certificate describes a one-processor schedule; this is the feasibility check of the certificate checker for the total discrepancy problem.
Formalization Note 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
/-- Overlap filter of the total-discrepancy certificate checker. With `N = |d| / 3`, the doubled
starting time of task `i` is `tᵢ = d_{3i+1}` and its doubled length is `2lᵢ`, `lᵢ = |c_{2+N+i}|`.
A polynomial-time stack program erases exactly the inputs `enc(c) ⊥ enc(d)` in which two tasks
`i < j` overlap (neither `tᵢ + 2lᵢ ≤ tⱼ` nor `tⱼ + 2lⱼ ≤ tᵢ`) and keeps every other input. -/
theorem tdCheck_overlap_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) ∧
¬(∀ i < d.length / 3, ∀ j < d.length / 3, i < j →
d.getD (3 * i + 1) 0 + 2 * (c.getD (2 + d.length / 3 + i) 0).natAbs ≤
d.getD (3 * j + 1) 0 ∨
d.getD (3 * j + 1) 0 + 2 * (c.getD (2 + d.length / 3 + j) 0).natAbs ≤
d.getD (3 * i + 1) 0)) → s ko = []) ∧
(¬(∃ (c : List ℤ) (d : List ℕ),
u = (encInts c).map (some ∘ Sum.inl) ++ none :: (encNats d).map (some ∘ Sum.inr) ∧
¬(∀ i < d.length / 3, ∀ j < d.length / 3, i < j →
d.getD (3 * i + 1) 0 + 2 * (c.getD (2 + d.length / 3 + i) 0).natAbs ≤
d.getD (3 * j + 1) 0 ∨
d.getD (3 * j + 1) 0 + 2 * (c.getD (2 + d.length / 3 + j) 0).natAbs ≤
d.getD (3 * i + 1) 0)) → s ko = u) := by sorry
end GTWSched.NPC