One block of FindOutPaths
ProvedDirKECC1549.Asm.fopBody_specFrom a state where blocks have been completed (FopRun), one iteration of the FindOutPaths loop either completes block (recording its candidate, with the time paid by the potential plus ) or stops (FopEnd), with time plus bounded by the potential plus , where every vertex has at most flipped out-entries.
Context. This lemma belongs to the machine-checked word-RAM implementation of Lemma 1 (p.11): Algorithm 1 refining by small -out sets, with the deterministic local search of [GKK+26, Proposition 6] (FindOutPaths and recursive path reversals). The program is written in the structured language Stmt compiled to the published word-RAM; Run E s mem Q states that the statement s, started on mem, reaches its end in a state satisfying Q t mem' within t ticks. The input cells double as registers; they are saved at SV and read through the image ImgAt. All definitions are in the Definitions.Def_DirKECC1549_Impl_* modules.
import Definitions.Def_DirKECC1549_Impl_L1Fop3
set_option autoImplicit false
open WordRAM Classical Finset
open DirKECC1549.Main DirKECC1549.Main.CostAux
open DirKECC1549 DirKECC1549.Asm
variable {w : Width} {n m : ℕ}theorem DirKECC1549.Asm.fopBody_spec (E : Env) (mm orig : Memory w) (hm : 0 < m) (P : LP) (B : Fin m → Fin n × Fin n)
(perm : Equiv.Perm (Fin m)) (F : Finset (Fin m)) (v s : Fin n) (pe0 : Fin n → Fin m)
(adj : Fin n → List (Fin m)) (D nb SA b : ℕ) (tb : ℕ → ℕ)
(hC : LsC P orig mm B perm F) (hA : AdjOK (flipEdges B F) adj)
(hadj : adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm) = adj)
(hR : FopRun hm P B perm F v s pe0 adj D SA (n + 1) mm b tb) (hb : b < nb) (hDpos : 1 ≤ D)
(h30 : (mm (P.SV + 30)).toNat = s) (h35 : (mm (P.SV + 35)).toNat = D) (h36 : (mm (P.SV + 36)).toNat = nb)
(h37 : (mm (P.SV + 37)).toNat = n + 1) (h39 : (mm (P.SV + 39)).toNat = SA)
(hSA : P.IP + m ≤ SA) (hw : 2 * SA + nb * (n + 1) + nb * D + n + 100 < 2 ^ w.bits)
(c0 : ℕ) (hF0 : ∀ x, cntF B perm F x 0 ≤ c0) :
Run E fopBody mm (fun t mm' => LsC P orig mm' B perm F ∧
(∀ a, KeepFo P m SA (nb * (n + 1)) a → mm' a = mm a) ∧
((mm' 0).toNat = 1 ↔ (mm' (P.SV + 34)).toNat = 0 ∧ b + 1 < nb) ∧
((∃ tb', FopRun hm P B perm F v s pe0 adj D SA (n + 1) mm' (b + 1) tb' ∧
t + psiD P B perm F (nb * D) ((dsStep (flipEdges B F) adj)^[tb' (b + 1)] (dsInit v pe0)) mm' ≤
psiD P B perm F (nb * D) ((dsStep (flipEdges B F) adj)^[tb b] (dsInit v pe0)) mm + 9 * (nb * D) + 127) ∨
(FopEnd hm P B perm F v s pe0 adj D nb SA (n + 1) mm' (b + 1) ∧
t + 50 * totF B perm F ≤ psiD P B perm F (nb * D) ((dsStep (flipEdges B F) adj)^[tb b] (dsInit v pe0)) mm +
9 * (nb * D) + 127 + 50 * (c0 * (nb * D + 1))))) := by sorry