Operational simulation between the two WordRAM models
OpenWordRAM.APSPBridge.uniform_operational_simulationfine-grained-complexitysimulationwordram
There is a natural overhead exponent such that 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 simulators 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. This is the operational half of the equivalence; it says nothing about transferring a runtime bound for a whole problem.
Preamble
import Definitions.Def_WordRAM_APSP_Bridge set_option autoImplicit false
Formal statement
theorem WordRAM.APSPBridge.uniform_operational_simulation : ∃ d : Nat, WordRAM.APSPBridge.UniformOperationalSimulation d := by sorry
Source
Torben Hagerup, Sorting and Searching on the Word RAM, STACS 1998, pp. 366-398, model conventions pp. 369-372, https://doi.org/10.1007/BFb0028575; Josh Alman and Virginia Vassilevska Williams, Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs, 2026, https://arxiv.org/abs/2610.06783; mission 'Two WordRAM models: equivalence with polylogarithmic overhead'.