Correctness of the CNF reduction for exact partitions with in-cluster centers
ProvedStableMSR.Recovery.Supplement.SATMetric.instance_correctalgorithmsclusteringcomputational-complexity
Every formula produces a valid rational metric with a positive threshold, including formulas with no clauses or an empty clause. The optimum over exactly k disjoint nonempty clusters with in-cluster centers is at most the threshold if and only if F is satisfiable.
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 instance_correct (F : PvsNP.CNF) :
(instanceOf F).Valid ∧
(optimumValue (instanceOf F).input.dist (instanceOf F).input.k ≤ ((instanceOf F).threshold : ℝ) ↔ PvsNP.Satisfiable F) := 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.