Charged parameter preparation and sparse recursive-root initialization
ProvedNearlyOptimalPPR.Computation.recursive_preparation_execFix an integer amplification constant and an input with , represented in the constant-size input layout with zero boundary counter. The recursive preparation routine has a finite execution. It computes the accessible depth , root threshold , scale , and binary rank , satisfying
It initializes a complete sparse representation of the source root state with queue mass at most one, amplified rank-array length, zero solve epoch, and bounded epoch marks. All work equals its instruction count, bounded by the explicit charged search, header, and sparse-initialization formula in the interface. It performs exactly one graph query and preserves existing output.
The result charges all scalar parameter searches and initializes only the seed-dependent sparse state.
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_runtime open Finset Matrix open scoped ENNReal set_option autoImplicit false noncomputable section attribute [local instance] Classical.propDecidable
namespace NearlyOptimalPPR.Computation
open SparseQueue
theorem recursive_preparation_exec (m : SolveModel) {n : ℕ} (g : InputGraph n) (ω : ℕ → Bool)
(B : ℕ) (hB : 1 ≤ B) (s : Fin n) (α ε : ℝ) (hε : 0<ε) (hε1 : ε ≤ 1)
(st : MachineState) (hh : st.scalar.halted=false) (input : PushInputMemory s α ε st)
(hBoundary : st.scalar.integerMemory 7=0) :
let ell := accessibleDepth (1/ε)
let q := rootThreshold ε ell
∃ (N r steps : ℕ) (out : MachineState), ∃ memory : RecursiveMachineMemory g s α ε ell (amplifiedQueueRank B r+1)
(recursiveInit g s q ell []) out,
MachineEval m g ω (recursivePreparationCode B) st steps out ∧
8 ≤ (N : ℝ)*q ∧ (N : ℝ) ≤ 8/q+1 ∧ 0<N ∧ N < 2^r ∧ r ≤ Nat.log 2 N+1 ∧
steps ≤ (12*(ell+2)^3+4*N+4*r+24)+(B+14)+
(12*(16*(ell+3))+64+(⌈1/q⌉₊+2)*(4*ell+22)+10*(amplifiedQueueRank B r+1)+264+
(21*(amplifiedQueueRank B r)+60*(16*(ell+3))+190)) ∧
memory.queueMass ≤ 1 ∧ out.scalar.core.ptrs 150=0 ∧ out.scalar.core.ptrs 151=1 ∧
out.scalar.core.ptrs 53=0 ∧ EpochInvariant (n:=n) (16*(ell+3)) out ∧
out.work=st.work+steps ∧ out.scalar.queries=st.scalar.queries+1 ∧ out.output=st.output ∧ out.scalar.halted=false := by sorry
end NearlyOptimalPPR.Computation