Reversing a stored path
ProvedDirKECC1549.Asm.tgP_specIf a slot at address stores a duplicate-free edge list , tgP toggles all edges of : afterwards the context holds for , 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_L1Tog
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.tgP_spec (E : Env) (mm orig : Memory w) (P : LP) (B : Fin m → Fin n × Fin n)
(perm : Equiv.Perm (Fin m)) (G : Finset (Fin m)) (hC : LsC P orig mm B perm G) (A : ℕ) (L : List (Fin m))
(hnd : L.Nodup) (h9 : (mm 9).toNat = A) (hA : (mm A).toNat = L.length)
(hL : ∀ i (hi : i < L.length), (mm (A + 1 + i)).toNat = L[i]) (hAm : P.IP + m ≤ A)
(hAw : A + L.length + 2 < 2 ^ w.bits) :
Run E tgP mm (fun t mm' => t ≤ 50 * L.length + 4 ∧ LsC P orig mm' B perm (xorS G L.toFinset) ∧
∀ a, TgKeep P m a → a ≠ 8 → a ≠ 9 → a ≠ 11 → mm' a = mm a) := by sorry