Finite binary multistack verifiers reduce to canonical binary SAT
ProvedPvsNP.finite_binary_verifiers_reduce_to_satalgorithmsclusteringcomputational-complexity
The time- and space-bounded Cook tableau of a finite multistack verifier is compiled to a binary CSP, then to canonical encoded CNF, producing a polynomial many-one reduction.
Preamble
import Definitions.Def_PvsNP import Definitions.Def_KMedianThreshold
Formal statement
theorem PvsNP.finite_binary_verifiers_reduce_to_sat (L : Language Bool)
(hL : L ∈ OAI.MetricKMedian.Complexity.NP) : PvsNP.PReducible L PvsNP.SAT := by
sorry
Source
Cook (STOC 1971). The verified CookProgram tableau compiler in the openai/math metric k-median development, and the PvsNP canonical binary CNF encoding.