Tagged-pair multistack NP embeds in finite binary-verifier NP
ProvedPvsNP.np_subset_finite_binary_verifiercomputational-complexityreductionsturing-machines
Each NP verifier in the tagged-pair PvsNP model can check the same language and witnesses in the length-prefixed binary comparator model. The recoding is polynomial on the full input alphabet, and the resulting verifier may use only finite physical work alphabets.
Preamble
import Definitions.Def_PvsNP import Definitions.Def_KMedianThreshold
Formal statement
theorem PvsNP.np_subset_finite_binary_verifier : PvsNP.NP ⊆ OAI.MetricKMedian.Complexity.NP := by sorry
Source
Cook, The complexity of theorem-proving procedures (STOC 1971). Mathlib Computability.TuringMachine.Computable. The finite-stack model and pair conventions are formalized in the Prove2Me PvsNP and OAI.MetricKMedian comparator definitions.