Charged construction and exact validity test for a graph-component search state
ProvedStableMSR.Recovery.Compiler.ComponentState.component_state_programThere is one deterministic program of instructions that constructs and tests a component state from ordinary graph input: a separator bitmap , a directed arc list for an undirected graph , a vertex , a width bound , and writable workspaces. Write and let be the length of the arc list. The arc list may have repetitions, and it contains every ordered adjacent pair.
Let be the vertices reachable from by a walk whose vertices avoid , and let be its external boundary. The program returns the exact zero-or-one acceptance flag for
Whenever the first two conditions hold, it constructs the characteristic bitmaps of both and . It therefore derives the component itself before checking its exact boundary; no component, boundary, connectivity certificate, or state-validity answer is supplied as input. The separator bitmap is preserved. The writable masks may initially contain arbitrary data, and the statement includes empty arc lists, width zero, oversized separators, and seeds lying inside the separator. A seed vertex requires .
The actual charged interpreter halts within
steps, including separator counting, complement-mask construction, all traversal scans, boundary construction, comparison, rejection branches, pointer restoration, and one final halt. All real data, oracle and random-tape counts, input metadata, and integer cells outside the designated work regions are preserved under the explicit array-separation conditions. The same code is chosen before or the graph data.
This supplies the construction and filtering kernel for an individual decomposition-search state. Iterating over all catalog separators and seeds, retaining the accepted state-pair records, evaluating their recurrence/DP values, geometric construction, and the complete clustering recovery program remain separate obligations.
import Definitions.Def_StableMSR_ComponentGraphMemory open scoped Classical open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.ComponentMemory
theorem StableMSR.Recovery.Compiler.ComponentState.component_state_program :
∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 161 ∧
∀ (n w : ℕ) (d : Point n → Point n → ℝ) (G : SimpleGraph (Fin n))
(S : Finset (Fin n)) (es : List (Fin n × Fin n)) (seed : Fin n) (s : Store),
s.ptrs 5 = (es.length:ℤ) → s.ptrs 6 = (n:ℤ) → s.ptrs 17 = (seed.val:ℤ) →
s.ptrs 43 = (w:ℤ) → Bitmap s.imem (s.ptrs 3) S → EdgeEncoding s.imem (s.ptrs 2) es →
Separate (n := n) (s.ptrs 3) (s.ptrs 4) →
Separate (n := n) (s.ptrs 3) (s.ptrs 50) → Separate (n := n) (s.ptrs 3) (s.ptrs 51) →
Separate (n := n) (s.ptrs 4) (s.ptrs 50) → Separate (n := n) (s.ptrs 50) (s.ptrs 51) →
EdgesSeparate (s.ptrs 2) (s.ptrs 4) es → EdgesSeparate (s.ptrs 2) (s.ptrs 50) es →
EdgesSeparate (s.ptrs 2) (s.ptrs 51) es →
(∀ e ∈ es, G.Adj e.1 e.2) → (∀ u v, G.Adj u v → (u,v) ∈ es) →
∀ (ω : ℕ → ℝ) (work : ℕ),
∃ t ≤ n*(17*es.length+43)+17*es.length+68,
let C := Finset.univ.filter (fun v : Fin n =>
∃ p : G.Walk seed v, ∀ z ∈ p.support, z ∉ S)
let B := Finset.univ.filter (fun v : Fin n => v ∉ C ∧ ∃ u ∈ C, G.Adj u v)
let result := (MinSumFPT.step P d ω)^[t] (s.state 0 work)
result.halted = true ∧ result.work = work+t ∧
result.cfg.ptrs 18 = (if seed ∉ S ∧ S.card ≤ w ∧ S = B then 1 else 0) ∧
(seed ∉ S → S.card ≤ w →
Bitmap result.imem (s.ptrs 50) C ∧ Bitmap result.imem (s.ptrs 51) B) ∧
Bitmap result.imem (s.ptrs 3) S ∧
(∀ x : ℤ, (∀ v : Fin n, x ≠ address (s.ptrs 4) v) →
(∀ v : Fin n, x ≠ address (s.ptrs 50) v) →
(∀ v : Fin n, x ≠ address (s.ptrs 51) v) → result.imem x = s.imem x) ∧
result.cfg.regs = s.regs ∧ result.cfg.mem = s.mem ∧
result.queries = s.queries ∧ result.tapePos = s.tapePos ∧
(∀ j : ℕ, j ∈ ([2,3,4,5,6,17,43,50,51]:List ℕ) → result.cfg.ptrs j = s.ptrs j) := by sorry