Proposition C.4 — symmetric stability recognition in coNP
ProvedStableMSR.Recovery.Supplement.recognition_coNPclusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stability
For every fixed rational , recognizing stability of rational finite metric MSR instances under arbitrary symmetric perturbations belongs to coNP:
Malformed strings and arrays that are not valid metrics are outside the language. This is the membership result for symmetric recognition in Theorem 5.1.
Differences from the source:
- encoding: Finite ordered metric input and unordered exact-k partitions → Fin n points, real metric arrays, and finite sets of nonempty disjoint blocks; reason: Input-order relabelling preserves every source instance and partition; base published definitions are reused without extra conditions
- encoding: Rational finite metric inputs, fixed rational gamma > 1 → The fixed binary instance language Recognize false gamma and the published CSPIdealMem.coNP; reason: The standard binary representation preserves all rational finite metrics and counts full input bit length; malformed strings are outside the language
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery.Supplement
theorem recognition_coNP (γ : ℚ) (hγ : 1 < γ) :
Recognize false γ ∈ CSPIdealMem.coNP := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Proposition C.4, p. 26; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e