Polynomial bit time for the explicit binary hub maps
ProvedStableMSR.Recovery.Supplement.HubReduction.maps_polytimeThe two explicit maps for Theorem 5.1 are polynomial-time string functions for each fixed rational stability factor greater than one, in the mission's multi-stack Turing machine model. They parse and validate the input, compute a rational maximum and the three gadget distances, and write a square table and optional labels. Their logical correctness on all strings is recorded separately.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_HubReduction set_option autoImplicit false
Formal statement
namespace StableMSR.Recovery.Supplement.HubReduction
theorem maps_polytime (γ : ℚ) (hγ : 1 < γ) :
PvsNP.PolyTimeComputable (verificationMap γ) ∧
PvsNP.PolyTimeComputable (recognitionMap γ) := by sorry
end StableMSR.Recovery.Supplement.HubReduction
Source
Ravichandran and Reyzin, arXiv:2611.03547, Theorem 5.1 and Appendix C, pp. 24–25, equations (3)–(5) and the bit-complexity observation after equation (4).