Polynomial bit time of the uniform rational instability checker
ProvedStableMSR.Recovery.Supplement.instability_checker_polytimeclusteringcomputational-complexityoptimization
For either perturbation convention, a deterministic polynomial-time multistack Turing machine computes the published two-string instability checker on every input and candidate certificate. The checker parses and validates the rational input and both labelings, checks all required distance inequalities, and compares the two sums of optimal in-cluster radii. The parameter is given in binary with the instance. This is the algorithmic assertion in the last paragraph of the proof of Lemma C.3.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false
Formal statement
namespace StableMSR.Recovery.Supplement theorem instability_checker_polytime (metric : Bool) : PvsNP.PolyTimeChecker (instabilityCheck metric) := by sorry end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.3, pp. 25–26 (bounded rational polyhedron and determinant argument). https://arxiv.org/abs/2611.03547