WordRAM simulation and runtime transfer with polylogarithmic overhead
OpenWordRAM.APSPBridge.uniform_simulation_and_transferThere is a single natural overhead exponent such that both of the following hold. First, every program of the unsigned-pointer WordRAM with multiplication has a fixed signed-pointer simulator, and conversely every signed-pointer program has a fixed unsigned-pointer simulator; the simulations preserve successful halting, accept/reject verdicts, and every mapped source memory cell, at target width , within steps for a positive constant fixed before the width and input. Second, for every problem whose input and observable output are bounded by , every input-magnitude exponent , and every correct source program with runtime at all sufficiently large word widths, there is a fixed target program, width threshold coefficient, and positive solving the same problem in steps, in both directions, including input packing and output recovery. This is the operational and quantitative core of the equivalence; it does not by itself assert the fine-grained threshold corollaries.
import Definitions.Def_WordRAM_APSP_Bridge set_option autoImplicit false
theorem WordRAM.APSPBridge.uniform_simulation_and_transfer : ∃ d : Nat, WordRAM.APSPBridge.UniformOperationalSimulation d ∧ WordRAM.APSPBridge.UniformTimeTransfer d := by sorry