Prove equivalence between two WordRAM models: one with unsigned pointers, bit operations, and shifts; the other with signed pointers and branching on sign. Both support bounded-word arithmetic and multiplication.
For input and observable output bounded by words, transfer running time in either direction to
including input/output conversion, with one bound valid for every sufficiently large word width. We preserve halting and mapped memory as well.
theorem WordRAM.APSPBridge.uniform_simulation_exists :
∃ d : Nat,
WordRAM.APSPBridge.UniformOperationalSimulation d ∧
WordRAM.APSPBridge.UniformTimeTransfer d ∧
WordRAM.APSPBridge.FineGrainedTimeEquivalence ∧
(WordRAM.APSPBridge.APSPBelow TrulySubcubicAPSP.APSP 3 ↔
WordRAM.APSPBridge.WordRAMBelow TrulySubcubicAPSP.APSP 3) ∧
((∃ r : Rat, r < 2 ∧ EndStatement.ThreeSum.SolvedInTime r) ↔
WordRAM.APSPBridge.WordRAMBelow
(WordRAM.APSPBridge.sourceProblem EndStatement.ThreeSum) 2) := by sorryThe WordRAM models with unsigned pointers and with signed pointers admit two-way simulation and complete runtime transfer, with one natural overhead exponent d. Both support multiplication; the former also provides bit operations and shifts, while the latter branches on sign. At the operational level, every native-free program in the former model and every program in the latter has a fixed simulator in the other, preserving and reflecting successful halting and preserving every mapped source memory cell at target width w+4, within C(t+w+1)(w+1)^d steps. Accept/reject verdicts are preserved explicitly.
For every problem Q with input and observable output bounded by B(n)=K(n+1)^q, every input-magnitude exponent κ, and every correct source program with time bound T(n) at all sufficiently large word widths, there are a fixed target program, width threshold coefficient, and positive C solving the same problem within C(T(n)+B(n)+1)(⌊log₂ n⌋+1)^d steps. This holds in both directions. The target starts from ordinary packed input and produces the required verdict and signed output; conversion and output recovery count toward the bound. The same bound works at every physical word width above the new threshold, including arbitrarily large widths.
Consequently, for every rational R>q, existence of an algorithm with some rational exponent below R is equivalent in the two models. As applications, the same main theorem includes integer APSP at threshold 3 and integer 3SUM at threshold 2. A positive subcubic or subquadratic exponent saving is therefore preserved. Exact exponent bounds may acquire a polylogarithmic factor; no equality of exact-exponent complexity classes is claimed.
The theorem asserts existence of simulators and transferred programs. It has no unproved transfer hypothesis and no hidden assumption that the source problem already has a fast algorithm: the concrete APSP and 3SUM conclusions are equivalences.