The terminal search of the local search
ProvedDirKECC1549.Asm.finP_specFrom a valid context with zero visited flags, the terminal search finP (a DFS from with budget ) reports in SV+42 whether it found a set: if the flag is 1, the discovered list holds a set containing , not , with no outgoing edge and volume below ; and the flag is 1 whenever such a set exists. Time at most , 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_L1Fin
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.finP_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) (D' : ℕ)
(hC : LsC P orig mm B perm F) (hZ : VisZero n P mm)
(hA : AdjOK (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm))) (hsv : s ≠ v)
(h29 : (mm (P.SV + 29)).toNat = v) (h30 : (mm (P.SV + 30)).toNat = s) (h35 : (mm (P.SV + 35)).toNat = D')
(hw : D' + 100 < 2 ^ w.bits) (c0 : ℕ) (hF0 : ∀ x, cntF B perm F x 0 ≤ c0) :
Run E finP mm (fun t mm' => LsC P orig mm' B perm F ∧ VisZero n P mm' ∧
(∀ a, KeepL P a → mm' a = mm a) ∧ FinOut P (flipEdges B F) v s D' mm' ∧
t ≤ 50 * (c0 * (D' + 1)) + 500 * D' + 400) := by sorry