Deterministic recovery program at each fixed rational stability parameter
OpenStableMSR.Recovery.rational_recovery_programThere are absolute positive integers such that, for every rational , one can choose a finite admissible deterministic program before seeing any input instance. For every finite real metric on points and every , the actual interpreter execution of halts within
steps and charged work, where is the exact Table 2 parameter envelope. Its output assigns each point a label in and uses every label. If the instance has a -stable optimum under arbitrary symmetric perturbations, the decoded output equals that optimum.
The constants are independent of . The same halting and output guarantees hold on unstable inputs, and the case is included. The program receives only the canonical inputs , with the two unused scalar slots fixed to zero; neither a stable optimum nor a certificate is input advice.
This is the remaining program-construction obligation for the recovery theorem, covering the deterministic search, local solver, order-family enumeration, and their implementation costs. The separate output-decoding lemma supplies feasibility from the validated labels; the separate parameter bound and rational calibration extend this statement to every real stability factor.
import Definitions.Def_StableMSR_Recovery_Execution set_option autoImplicit false open scoped Classical
namespace StableMSR.Recovery
/-- Uniform deterministic programs for rational stability parameters. The program
is selected before any input instance, and its charged interpreter execution
writes all k nonempty cluster labels. -/
theorem rational_recovery_program :
∃ a b : ℕ, 0 < a ∧ 0 < b ∧
∀ ε₀ : ℚ, 0 < ε₀ → ε₀ < 1 →
∃ P : MinSumFPT.Program, DeterministicProgram P ∧
∀ (n k : ℕ) (d : Point n → Point n → ℝ),
1 ≤ k → k ≤ n → IsMetricArray d →
∃ t ≤ a * n ^ (b * parameterEnvelope (ε₀ : ℝ)),
let s := execute P n k d t
s.halted = true ∧
s.work ≤ a * n ^ (b * parameterEnvelope (ε₀ : ℝ)) ∧
ValidLabels n k s ∧
∀ O, Stable d k (1 + (ε₀ : ℝ)) O → outputPartition n k s = O := by sorry
end StableMSR.Recovery