Theorem 5.1 — recognition and verification complexity
ProvedStableMSR.Recovery.Supplement.recognition_verification_complexityFix a rational . On rational finite metric inputs, specified-partition verification is coNP-complete under both arbitrary symmetric and metric perturbations. Recognition is coNP-complete for arbitrary symmetric perturbations and coNP-hard for metric perturbations:
In all four cases the complement of exact MSR threshold decision reduces by polynomial-time many-one maps to the stability language. One map supplies a specified target and the associated instance projection supplies recognition. On every valid threshold input the supplied partition is the unique unperturbed optimum and has exactly one nonsingleton cluster.
The reductions hold on all binary strings, including malformed source strings. Perturbations may be real and centers may change. No NP-hardness premise or complexity-class separation is assumed. This is an independent complexity companion to the recovery goal.
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-input recognition and verification with polynomial-time many-one reductions → Four explicit binary languages using the published PvsNP reductions and CSPIdealMem coNP notions; reason: Malformed strings are outside each language; the complements and reductions quantify over all strings
- encoding: The reduction supplies the unique original optimum with exactly one nonsingleton cluster → A common specified-target map f and an instance map g, polynomial-time and satisfying all four equivalences, with the supplied-output clause on every valid threshold input; reason: The two codomains require different encodings; g is the instance projection on valid threshold data and all supplied properties remain conclusions
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false open scoped Classical
namespace StableMSR.Recovery.Supplement
theorem recognition_verification_complexity (γ : ℚ) (hγ : 1 < γ) :
CSPIdealMem.CoNPComplete (Verify false γ) ∧
CSPIdealMem.CoNPComplete (Verify true γ) ∧
CSPIdealMem.CoNPComplete (Recognize false γ) ∧
CoNPHard (Recognize true γ) ∧ SuppliedReduction γ := by sorry
end StableMSR.Recovery.Supplement