An inner level of the local search
ProvedDirKECC1549.Asm.lsInner_specAt level (with the procedure correct at level ), the inner level runs FindOutPaths with blocks of explorations, then iterates over the stored candidates; it reports correct sets, finds a set whenever a good history exists, keeps the frame cells, and takes at most ticks.
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_L1Ls3
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.lsInner_spec (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 sl : ℕ) (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)
(i : ℕ) (hi : i < K)
(hcall : ∀ (F' : Finset (Fin m)) (q : Memory w), LPre P orig B perm v s K Δ FR W (i + 1) F' q →
Run E .call q (fun t q' => LPost P orig B perm v s K Δ FR W sl (i + 1) F' q t q'))
(F : Finset (Fin m)) (q : Memory w) (hpre : LPre P orig B perm v s K Δ FR W i F q)
(h0 : (q 0).toNat = i) (h1 : (q 1).toNat = K) :
Run E lsInner q (fun t q' => LsC P orig q' B perm F ∧ VisZero n P q' ∧
(∀ a, KeepLS P m FR W K i a → q' a = q a) ∧ q' (FR + i * W) = q (FR + i * W) ∧
(q' 5).toNat = FR + i * W ∧ (q' (P.SV + 38)).toNat = FR + i * W ∧ LsFound P B v s K Δ q' ∧
(LsGood B v s K Δ F i → (q' (P.SV + 42)).toNat = 1) ∧
t ≤ lsFopT K Δ (2 * (K - i) + 1) +
(2 * (K - i) + 1) * (100 * ((2 * (K - i) + 1) * (Δ + 1)) + lsTT K Δ sl (K - (i + 1)) + 102) + 70) := by sorry