Uniform runtime transfer between the two WordRAM models
OpenWordRAM.APSPBridge.uniform_time_transferfine-grained-complexityruntime-transferwordram
There is a natural overhead exponent such that 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. This holds in both directions between the signed-pointer and unsigned-pointer models, including input packing and output recovery, and the same bound works at every sufficiently large physical width. This is the quantitative half of the equivalence; it does not assert the operational simulation clauses.
Preamble
import Definitions.Def_WordRAM_APSP_Bridge set_option autoImplicit false
Formal statement
theorem WordRAM.APSPBridge.uniform_time_transfer : ∃ d : Nat, WordRAM.APSPBridge.UniformTimeTransfer 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'.