Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Linear-time Word-RAM reverse search with a local discovery certificate

Open
DirKECC1549.Main.reverse_search_discovery_program

by parclytaxel · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

directed-graphsgraph-algorithmsword-ram

For a finite directed multigraph with n vertices and m edges, and a root r, a single multiplication Word-RAM program returns parent pointers and admits a finite discovery-list certificate L. The list is a mathematical witness; it need not be stored in the output.

The parent of r is r. The list has no repeated vertices, contains r, and is closed under incoming edges:

(u,v)∈E,v∈L⟹u∈L.(u,v)\in E,\quad v\in L\quad\Longrightarrow\quad u\in L.(u,v)∈E,v∈L⟹u∈L.

For every vertex v in L other than r, its parent occurs strictly before the first occurrence of v in L and is joined to it by an original graph edge:

(v,par(v))∈E,par(v)∈L[0:indexL(v)].(v,\mathrm{par}(v))\in E,\qquad \mathrm{par}(v)\in L[0:\mathrm{index}_L(v)].(v,par(v))∈E,par(v)∈L[0:indexL​(v)].

Every vertex, including those outside L, has a valid parent identifier written into the designated parent array. No claim involving graph reachability or an externally supplied rank function is assumed in this certificate.

One fixed program, one polynomial capacity function, and one positive absolute constant c work for all graphs, roots, arbitrary natural parameters k and Delta, and all admissible word widths. The program halts within c(m+n) ticks, preserves the graph layout and all three scalar parameters, and tolerates arbitrary initial contents of other cells. The input-size parameter is 8(n+2m+3)+k+Delta, exactly as in the parent forest contract.

This local discovery certificate separates the machine implementation of reverse exploration from the graph-theoretic proof of reachability and decreasing parent ranks.

Preamble
import Definitions.Def_DirKECC1549_Main_Machine
set_option autoImplicit false
open WordRAM
Formal statement
namespace DirKECC1549.Main

theorem reverse_search_discovery_program :
    ∃ (A : Complexity.Algorithm .multiplication) (c : ℝ), 0 < c ∧
      ∀ (n m : ℕ) (G : Fin m → Fin n × Fin n) (k Δ : ℕ) (r : Fin n),
        Implements A (8 * blk n m + k + Δ)
          (fun _ mem => GraphLayout G mem ∧ (mem (paramCell n m 0)).toNat = k ∧
            (mem (paramCell n m 1)).toNat = Δ ∧ (mem (paramCell n m 2)).toNat = r)
          (c * ((m + n : ℕ) : ℝ))
          (fun _ mem => (GraphLayout G mem ∧ (mem (paramCell n m 0)).toNat = k ∧
            (mem (paramCell n m 1)).toNat = Δ ∧ (mem (paramCell n m 2)).toNat = r) ∧
            ∃ (par : Fin n → Fin n) (order : List (Fin n)), par r = r ∧
              order.Nodup ∧ r ∈ order ∧
              (∀ e : Fin m, (G e).2 ∈ order → (G e).1 ∈ order) ∧
              (∀ v ∈ order, v ≠ r →
                (∃ e, G e = (v, par v)) ∧ par v ∈ order.take (order.idxOf v)) ∧
              ∀ v : Fin n, (mem (arrayCell n m v)).toNat = par v) := by sorry

end DirKECC1549.Main
Source
Derived local-invariant implementation obligation for DirKECC1549.Main.reverse_search_forest_program, https://prove2.me/theorems/15c280d4-35d0-4f4a-ab6d-22bc4274cdd5, using the published GraphLayout, Implements and runFrom definitions. The parent cites Georgiadis et al., STOC 2027 submission #1549, Section 3.2.1, Lemma 2 construction, pp. 13–14 (reverse graph search from the root).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me