NP-hardness of the rational exact MSR threshold language
ProvedStableMSR.Recovery.Supplement.threshold_np_hardEvery language in NP has a polynomial-time many-one reduction to exact MSR threshold decision in the mission's binary encoding. The output language uses positive rational thresholds, rational finite metrics, exactly the requested number of nonempty blocks and centers drawn from their blocks. This is the source hardness result used in Appendix C.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false
Formal statement
namespace StableMSR.Recovery.Supplement
theorem threshold_np_hard :
∀ L ∈ PvsNP.NP, PvsNP.PReducible L MSRThreshold := by sorry
end StableMSR.Recovery.Supplement
Source
Gibson, Kanade, Krohn, Pirwani and Varadarajan, On Metric Clustering to Minimize the Sum of Radii, Algorithmica 57 (2010), 484–498, DOI 10.1007/s00453-009-9282-7, Section 3 of the author version. Ravichandran and Reyzin, arXiv:2611.03547, Appendix C, pp. 23–24, give the ball-to-partition correspondence.