A charged program for external boundaries, cardinalities, and least vertices
ProvedStableMSR.Recovery.Compiler.BoundaryStatsProgram.boundary_statistics_programThere is a single deterministic program with instructions that computes the external neighborhood of a vertex set, its cardinality, and its least vertex from ordinary graph data. For a simple graph on vertices and a set , write
The input consists of a zero–one bitmap for and a directed edge list of length containing exactly graph adjacencies, with every adjacency represented in both orientations. The writable output bitmap is disjoint from these input arrays; its initial contents are arbitrary. Edge order and duplicates are unrestricted.
The program initializes the output bitmap, scans the edge array to compute , and scans the resulting bitmap for its cardinality and least vertex. The entire composed program, including pointer redirection/restoration and one final halt, takes exactly
charged interpreter steps. The output bitmap is exactly the characteristic function of . Register contains , while register contains its least vertex or the sentinel exactly when is empty. The initial graph pointers and dimensions, all integer cells outside the output bitmap, all real registers and memory, and oracle/tape counts are preserved.
The result covers , empty boundaries, and arbitrary initial output contents and work counters. This supplies concrete boundary construction and size/representative extraction for decomposition search. It does not assume a precomputed boundary, implement subset ranking or bitmap comparison, or establish the full clustering recovery program.
import Definitions.Def_StableMSR_ComponentGraphMemory import Mathlib.Combinatorics.SimpleGraph.Basic open scoped Classical open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.ComponentMemory
theorem StableMSR.Recovery.Compiler.BoundaryStatsProgram.boundary_statistics_program :
∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 58 ∧
∀ (n : ℕ) (d : Point n → Point n → ℝ) (G : SimpleGraph (Fin n))
(C : Finset (Fin n)) (es : List (Fin n × Fin n)) (s : Store),
s.ptrs 5 = (es.length:ℤ) → s.ptrs 6 = (n:ℤ) →
Bitmap s.imem (s.ptrs 3) C → EdgeEncoding s.imem (s.ptrs 2) es →
Separate (n := n) (s.ptrs 3) (s.ptrs 4) →
EdgesSeparate (s.ptrs 2) (s.ptrs 4) es →
(∀ e ∈ es, G.Adj e.1 e.2) → (∀ u v, G.Adj u v → (u,v) ∈ es) →
∀ (ω : ℕ → ℝ) (work : ℕ),
let B := Finset.univ.filter (fun v : Fin n => v ∉ C ∧ ∃ u ∈ C, G.Adj u v)
let result := (MinSumFPT.step P d ω)^[13*n+17*es.length+22] (s.state 0 work)
result.halted = true ∧ result.work = work+(13*n+17*es.length+22) ∧
result.queries = s.queries ∧ result.tapePos = s.tapePos ∧
result.cfg.mem = s.mem ∧ result.cfg.regs = s.regs ∧
(∀ v : Fin n, result.imem (address (s.ptrs 4) v) =
if v ∉ C ∧ (∃ u ∈ C, G.Adj u v) then 1 else 0) ∧
result.cfg.ptrs 18 = (B.card:ℤ) ∧
(result.cfg.ptrs 19 = (n:ℤ) ↔ B = ∅) ∧
(B.Nonempty → ∃ v ∈ B, result.cfg.ptrs 19 = (v.val:ℤ) ∧
∀ u ∈ B, v.val ≤ u.val) ∧
(0 ≤ result.cfg.ptrs 19 ∧ result.cfg.ptrs 19 ≤ (n:ℤ)) ∧
(∀ x : ℤ, (∀ v : Fin n, x ≠ address (s.ptrs 4) v) → result.imem x = s.imem x) ∧
(∀ j : ℕ, 2 ≤ j → j ≤ 6 → result.cfg.ptrs j = s.ptrs j) := by sorry