Polynomial-time Boolean-stack programs for the MSR verifier and specified input validator
ProvedStableMSR.Recovery.Supplement.BinaryVerifier.check_polynomialalgorithmsclusteringcomputational-complexity
The total numeric and parsing algorithms have polynomial-time finite Boolean-stack programs, on the standard self-delimiting runtime encodings of lists and products. The programs include all decoding, validation, and exact rational arithmetic, and cover arbitrary input strings.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryVerifier import Definitions.Def_QuantumMaxCutFiniteNumericRuntime set_option autoImplicit false open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery.Supplement
Formal statement
namespace StableMSR.Recovery.Supplement.BinaryVerifier
theorem check_polynomial :
(∀ metric, Poly (check metric)) ∧ Poly specifiedOK := by sorry
end StableMSR.Recovery.Supplement.BinaryVerifier
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.3 and Theorem 5.1. https://arxiv.org/abs/2611.03547