The Gauss–Jordan straight-line program is well-formed with respect to its time stamps
ProvedOPI.GEP.prog_timeOKOblivious Gauss–Jordan elimination on an augmented system, followed by an output map , is written as a straight-line program over a field . Each instruction has a destination id, a list of source ids and an operation. Ids have the form with and , so the time stamp of an id is . Ids (time stamp ) are inputs. The program has time stamps, where .
Hypotheses. , and for every row and column the sources of the instruction that loads the initial entry are distinct input ids ().
Statement. The program satisfies . That is:
- every source of every instruction is an input or the destination of some instruction of the program, has strictly smaller time stamp than the instruction's destination, and is ;
- each instruction has pairwise distinct sources;
- no destination is an input id, and every destination is ;
- all destinations of the program are pairwise distinct;
- time stamps of destinations are nondecreasing along the program.
By the general criterion pwf_of_time this yields well-formedness (prog_pwf). The program can then be evaluated as a fixpoint, giving prog_out: the outputs are the prescribed linear combinations of the particular solution. This is how the classical decoder is compiled to a reversible circuit.
import Definitions.Def_TwoFoldOPI_CL_Part01
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI OPI.GEP
variable {K : Type} [Field K] [DecidableEq K]
variable (R C Kd : ℕ) (coef : ℕ → ℕ → K) (a0src : ℕ → ℕ → List ℕ) (a0op : ℕ → ℕ → List K → K)
theorem OPI.GEP.prog_timeOK (hKd : Kd ≤ C)
(ha0 : ∀ i < R, ∀ l ≤ C, (∀ s ∈ a0src i l, s < Wd R C) ∧ (a0src i l).Nodup) :
TimeOK (Tmax R C Kd * Wd R C) (fun x => x < Wd R C) (tm R C) (prog R C Kd coef a0src a0op) := by sorry