Lemma 5, implementation: Algorithm 3 on the word-RAM within a constant factor of its charged cost
ProvedDirKECC1549.Main.lemma_5_implAlgorithm 3 can be implemented on the word-RAM within a constant factor of the cost charged in the proof of Lemma 5. There are one word-RAM program and one absolute constant such that, for every and every directed multigraph with vertices and edges, the program, started on the encoding of , performs a run of Algorithm 3 of some cost (in the sense of Alg3CostRun). It halts within ticks, and its output labels are the output of that run.
This is the implementation half of Lemma 5 (pp.18–19). Every line of Algorithm 3 is carried out within the time the proof of Lemma 5 charges for it:
- strongly connected components and the recursion on (lines 1–4, Tarjan);
- the call with (line 7);
- Lemma 1 in time (line 8);
- the hitting sets of Lemma 2 in time (line 9);
- Lemma 3 in time per hitting-set vertex (line 11);
- the recursive calls on the residual graphs (line 13);
- the common refinements in time each (p.16).
Formalization note. The input convention is that of Lemma 5: in cell , labels in cells .
Preamble
import Mathlib import Definitions.Def_DirKECC1549_Main_Machine import Definitions.Def_DirKECC1549_Main_Alg3Cost set_option autoImplicit false open WordRAM
Formal statement
namespace DirKECC1549.Main
theorem lemma_5_impl :
∃ (A : Complexity.Algorithm .multiplication) (c : ℝ), 0 < c ∧
∀ (k n m : ℕ) (G : Fin m → Fin n × Fin n), 1 ≤ k → 1 ≤ n →
∃ T : ℕ, HaltsWithin A.code (A.width (kInputLength n m k)) (kInput _ n m k G) (c * T)
(fun mem => Alg3CostRun n m G k (labelRel mem (kInputLength n m k)) T) := by sorry
end DirKECC1549.Main
Source
Georgiadis, Kipouridis, Kosinas, Papadopoulos, Pergaminelis, STOC 2027 submission #1549, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1549.pdf, Section 3.3, Lemma 5 and its proof (pp.18-19)