A wrapped local search
ProvedDirKECC1549.Asm.wrap_coreAfter loading the base registers, a call of the local search from level 0 with empty flipped set returns with the context restored, zero visited flags, correct found sets, completeness for -out sets of volume , and time at most plus the wrapper cost.
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_L1Wrap
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.wrap_core (E : Env) (orig : Memory w) (hm : 0 < m) (P : LP) (B : Fin m → Fin n × Fin n)
(perm : Equiv.Perm (Fin m)) (v s : Fin n) (K Δ FR W : ℕ) (hL : LsLay P n m K Δ FR W w.bits) (hsv : s ≠ v)
(hcut : ∀ X : Finset (Fin n), v ∈ X → s ∉ X → K ≤ outCount B X)
(hE : EnvOK E lsBody) (hs : ∀ x ∈ E.sites, x < 2 ^ w.bits)
(c : List CI) (hc : ∀ i ∈ c, Straight i) (mm : Memory w)
(hctx : LsCtx P orig mm B perm) (hZ : VisZero n P mm) (hG : LsGlob P v s K Δ W mm)
(hregs : LsRegs P (foldM c mm)) (h5 : (foldM c mm 5).toNat = FR) (h3 : (foldM c mm (FR + 3)).toNat = 0)
(h38 : (foldM c mm (P.SV + 38)).toNat = FR)
(hfr : ∀ a, a ≠ 0 → a ≠ 5 → (a < 13 ∨ 25 < a) → a ≠ FR + 3 → a ≠ P.SV + 38 → foldM c mm a = mm a) :
Run E (.seq (.code c) .call) mm (fun t mm' => LsCtx P orig mm' B perm ∧ VisZero n P mm' ∧
(∀ a, KeepLS P m FR W K 0 a → (a = 27 ∨ 28 ≤ a) → mm' a = mm a) ∧ LsFound P B v s K Δ mm' ∧
((∃ S : Finset (Fin n), v ∈ S ∧ s ∉ S ∧ outCount B S = K ∧ vol B S ≤ Δ) → (mm' (P.SV + 42)).toNat = 1) ∧
t ≤ c.length + lsTT K Δ E.sites.length K) := by sorry