Polynomial binary preimages of stability verification lie in coNP
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.verification_preimage_coNPalgorithmsclusteringcomputational-complexity
For a polynomially computed binary string map, the preimage of specified-partition stability verification is in the native coNP class. The verifier rejects invalid claimed instability certificates and uses a polynomial in the original input length, also on the empty and one-bit words.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryRecovery 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.verification_preimage_coNP
(metric : Bool) (γ : ℚ) (hγ : 1 < γ) (g : Bits → Bits) (hg : Poly g) :
({w | g w ∈ Verify metric γ} : Language Bool) ∈ CSPIdealMem.coNP := by
sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Theorem 1.1, Appendix A.5 (bit complexity), and Proposition C.4. https://arxiv.org/abs/2611.03547