Local search in the reverse graph
ProvedDirKECC1549.Asm.wrapR_specWith in SV+29, SV+30 and every set separating from having at least outgoing edges in , wrapR runs the local search in : the dynamic facts and cells are kept, a reported set is a -out set of of volume containing and not , a set is reported whenever one with exactly outgoing edges exists, within 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_L1Alg1
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.wrapR_spec (E : Env) (orig : Memory w) (hm : 0 < m) (P : LP) (OR PR IR HR TR : ℕ)
(G : Fin m → Fin n × Fin n) (σ τ : Equiv.Perm (Fin m)) (K Δ FR W : ℕ)
(hst : AlgStat P OR PR IR HR TR orig G σ τ) (hL : LsLay P n m K Δ FR W w.bits)
(hE : EnvOK E lsBody) (hs : ∀ x ∈ E.sites, x < 2 ^ w.bits)
(mm : Memory w) (hdyn : AlgDyn (n := n) P orig mm) (hZ : VisZero n P mm)
(hc : AlgCells (n := n) P OR PR IR HR TR FR K Δ W mm) (a b : Fin n) (hab : b ≠ a)
(h29 : (mm (P.SV + 29)).toNat = a) (h30 : (mm (P.SV + 30)).toNat = b)
(hcut : ∀ X : Finset (Fin n), a ∈ X → b ∉ X → K ≤ outCount (Rev G) X) :
Run E wrapR mm (fun t mm' => AlgDyn (n := n) P orig mm' ∧ VisZero n P mm' ∧
(∀ x, KeepLS P m FR W K 0 x → (x = 27 ∨ 28 ≤ x) → mm' x = mm x) ∧ LsFound P (Rev G) a b K Δ mm' ∧
((∃ S : Finset (Fin n), a ∈ S ∧ b ∉ S ∧ outCount (Rev G) S = K ∧ vol (Rev G) S ≤ Δ) →
(mm' (P.SV + 42)).toNat = 1) ∧
t ≤ 42 + lsTT K Δ E.sites.length K) := by sorry