A linear-time input adapter for Cook checking relations
ProvedStableMSR.Recovery.Supplement.BinaryVerifier.tagged_checker_of_polyalgorithmsclusteringcomputational-complexity
Any polynomial-time Boolean-stack program for a Boolean predicate of two bitstrings gives a polynomial-time machine in the mission’s Cook checker model. A linear-time input adapter reads the tagged four-symbol alphabet and writes the runtime’s framed binary pair. The remainder is composition of the two certified machines.
Preamble
import Definitions.Def_PvsNP import Definitions.Def_QuantumMaxCutFiniteNumericRuntime set_option autoImplicit false open OAI.MetricKMedian.Binary.Automatic
Formal statement
namespace StableMSR.Recovery.Supplement.BinaryVerifier theorem tagged_checker_of_poly (f : List Bool × List Bool → Bool) (hf : Poly f) : PvsNP.PolyTimeChecker f := by sorry end StableMSR.Recovery.Supplement.BinaryVerifier
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.3 and Theorem 5.1. https://arxiv.org/abs/2611.03547