Fine-grained time equivalence above the I/O exponent
OpenWordRAM.APSPBridge.fine_grained_time_equivalencefine-grained-complexitytime-equivalencewordram
For every problem whose input length is at most and whose output predicate depends only on the first output entries, and for every rational threshold , the following are equivalent: is solvable in the signed-pointer WordRAM model at some rational exponent , and is solvable in the unsigned-pointer WordRAM model at some rational exponent . Exact exponent bounds are not compared: a solver on one side may be transferred to the other with a polylogarithmic factor, so only existence below the threshold is asserted.
Preamble
import Definitions.Def_WordRAM_APSP_Bridge set_option autoImplicit false
Formal statement
theorem WordRAM.APSPBridge.fine_grained_time_equivalence : WordRAM.APSPBridge.FineGrainedTimeEquivalence := by sorry
Source
Torben Hagerup, Sorting and Searching on the Word RAM, STACS 1998, pp. 366-398, 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'.