Binary SAT Karp-reduces to rational exact sum-of-radii threshold decision
ProvedStableMSR.Recovery.Supplement.SATMetric.sat_reduces_thresholdalgorithmsclusteringcomputational-complexity
There is a polynomial-time many-one reduction on all binary strings from the mission’s binary CNF satisfiability language to rational minimum sum-of-radii threshold decision. The target has an explicit full integer-valued distance matrix, and its centers belong to its exact-k partition blocks.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_SATMetric set_option autoImplicit false open StableMSR.Recovery StableMSR.Recovery.Supplement
Formal statement
namespace StableMSR.Recovery.Supplement.SATMetric theorem sat_reduces_threshold : PvsNP.PReducible PvsNP.SAT MSRThreshold := by sorry end StableMSR.Recovery.Supplement.SATMetric
Source
Gibson, Kanade, Krohn, Pirwani, and Varadarajan, On Metric Clustering to Minimize the Sum of Radii, Algorithmica 57 (2010), Section 3, Theorem 2. https://www.cs.utsa.edu/~gibson/MetricKClustering.pdf . Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Appendix C, https://arxiv.org/abs/2611.03547 . The explicit table used here adapts the literal and private-point construction to unrestricted finite metrics.