Subset Sum in word-RAM steps (poly-free, )
OpenSubsetSum.MITM.Race.boundThere is one finite deterministic program for the Big O Speedrun subset-sum model that decides every instance with and runs in
steps, so that for every with a single . This is exactly: no polynomial factor, hence strictly better than the classic bound of Horowitz and Sahni (1974), whose probe cost squares to and so does not satisfy the definition at .
Why the polynomial must vanish. At the definition reads with no threshold and no slack, so any factor in squares to an unbounded factor on . Sorted meet-in-the-middle with binary-search probes, radix sorting on half-word digits, and any per-subset bit extraction are therefore unlistable at in this model.
The construction. Both halves' subset sums are built by doubling merge (a geometric sum, ) rather than sorted from scratch, and complements are found by a single linear two-pointer sweep over the two sorted arrays: on increment , on decrement , on equality accept. Each step eliminates one row or one column, so the sweep is linear. Every instruction, including the word comparison, costs one step regardless of the input bit length , so the same bound serves every in .
A second, independent construction reaches the same exponent by direct addressing: mark each left-half sum with one store at and probe with one load at , giving flat cost . Both are poly-free; the merge-and-sweep program is the one formalized here.
The program never draws a random word, so correctness is deterministic although the model is randomized. Proof: 27 modules of core Lean (no Mathlib), about 16,900 lines.
import Definitions.Def_BigOSpeedrunSubsetSum
theorem SubsetSum.MITM.Race.bound : BigOSpeedrun.SubsetSum.SolvedInTime (1 / 2 : Rat) := by sorry