Total discrepancy checker: polynomial-time length filter
ProvedGTWSched.NPC.tdCheck_len_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 .
There is a structured multi-stack program (hence, by stack_program_polytime, a polynomial-time Turing machine) whose number of steps on an input is at most for a constant , and which outputs itself if
- for some integer list and natural-number list ,
- every entry of is positive,
- , and
- ,
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 with positive entries and whose certificate has 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.
import Mathlib import Definitions.Def_CookPvsNP_StackProgram import Definitions.Def_ProjSchedTW_Complexity_Encoding open CookPvsNP
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