A block of search steps
ProvedDirKECC1549.Asm.dsBlk_specRunning dsBlk from a state reached after steps performs DFS steps as long as dsCond holds and stops at the first state violating it, at step ; it records the least stack height over the block in SV+32, keeps the context cells, never exceeds the budget, and its time plus the potential psiD at the end is at most the potential at the start plus 30.
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_L1Blk
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.dsBlk_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) (Tb T t0 : ℕ)
(hC : LsC P orig mm B perm F)
(hA : AdjOK (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))
(hD : DRep hm P B perm F 1 v
((dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t0] (dsInit v pe0)) mm)
(hTb : (mm (P.SV + 31)).toNat = Tb) (hs : (mm (P.SV + 30)).toNat = s)
(hmin : (mm (P.SV + 32)).toNat =
((dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t0] (dsInit v pe0)).stk.length)
(hTT : Tb ≤ T)
(hc0 : ((dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t0]
(dsInit v pe0)).cnt ≤ Tb) :
Run E dsBlk mm (fun t mm' => ∃ t1, t0 ≤ t1 ∧
DRep hm P B perm F 1 v
((dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t1] (dsInit v pe0)) mm' ∧
¬ dsCond Tb s ((dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t1]
(dsInit v pe0)) ∧
(∀ u, t0 ≤ u → u < t1 → dsCond Tb s
((dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[u] (dsInit v pe0))) ∧
(mm' (P.SV + 32)).toNat = minUpTo (fun u => ((dsStep (flipEdges B F)
(adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t0 + u] (dsInit v pe0)).stk.length) (t1 - t0) ∧
(∀ a, KeepB P a → mm' a = mm a) ∧
((dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t1]
(dsInit v pe0)).cnt ≤ Tb ∧
t + psiD P B perm F T ((dsStep (flipEdges B F)
(adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t1] (dsInit v pe0)) mm' ≤
psiD P B perm F T ((dsStep (flipEdges B F)
(adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))^[t0] (dsInit v pe0)) mm + 30) := by sorry