Stability recognition belongs to coNP for γ ≥ (3+√5)/2, for arbitrary k
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.recognition_coNP_common_thresholdalgorithmsclusteringcomputational-complexity
For arbitrary k and all fixed rational γ>1 with (γ−1)² ≥ γ, there is a direct bit-polynomial recovery program on valid stable instances. Consequently recognition under symmetric perturbations is in coNP in this range.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_CandidateSelection import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.recognition_coNP_common_threshold (γ : ℚ) (hγ : 1 < γ) (hgap : γ ≤ (γ-1)^2) : (∃ f : Input → List ℕ, Poly f ∧ Recovers f γ) ∧ Recognize false γ ∈ CSPIdealMem.coNP := by sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Section 3 and Appendix C.4. https://arxiv.org/abs/2611.03547 . The common-radius two-edge criterion is deduced from the published center and intercluster separation statements.