Canonical CNF decoding and polynomial bit time of the SAT-to-MSR map
ProvedStableMSR.Recovery.Supplement.SATMetric.codec_and_runtimealgorithmsclusteringcomputational-complexity
The two delimiter levels and signed binary variable indices round-trip on every canonical formula. A polynomial-time multistack machine computes the full reduction on all bitstrings, including those with malformed codes and large binary variable names.
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 codec_and_runtime :
(∀ F : PvsNP.CNF, parse (PvsNP.encodeCNF F) = F) ∧ PvsNP.PolyTimeComputable reduce := 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.