Subset Sum in $O(2^{0.49n})$ time

The explanation

Take six numbers: 3, 34, 4, 12, 5 and 2. Can some of them add up to exactly 9? Yes: 4 + 5 works, and so does 3 + 4 + 2. This puzzle is called Subset Sum. You get a list of positive whole numbers and a target. You ask whether some selection of the numbers hits the target exactly. The blunt method tries every selection. Six numbers allow 2 to the power 6, or 64, selections. Each extra number doubles that count. With 100 numbers there are about 1.27 × 10^30 selections. Below, n means how many numbers the list holds.

A faster method is the meet-in-the-middle algorithm of Horowitz and Sahni, from 1974. Split the list into two halves. List every sum each half can make. In the example, 3, 34 and 4 make eight sums: 0, 3, 4, 7, 34, 37, 38 and 41. The half 12, 5 and 2 makes eight more: 0, 2, 5, 7, 12, 14, 17 and 19. Now look for one sum from each side that totals 9. The pair 4 and 5 works, and so does 7 and 2. Two lists of 8 replace one list of 64. In general the work grows like 2 to the power n/2. For 100 numbers, that is about 1.13 × 10^15 instead of 10^30.

Subset Sum is one of the classic NP-complete problems, on Karp's 1972 list. NP-complete means it belongs to a large family of problems that no one knows how to solve quickly. Since 1974, 2 to the power n/2 has been the familiar time scale. In 1981, Schroeppel and Shamir kept that time while using far less memory. In 2023, Chen, Jin, Randolph and Servedio cut the time by a growing factor. In certain computer models, their time is 2 to the power n/2, divided by n to a power above 0.5023. That leaves the exponent at one half. The paper calls a fixed cut in the exponent itself a different objectiveSource 1.

Why was the exponent so stubborn? Faster tricks existed, but only for random inputs. Howgrave-Graham and Joux wrote one solution in many ways. Then they searched only a filtered share of those ways. The paper notes that those gains concern random instances, not a guarantee for every inputSource 2. A worst-case algorithm must work on every list, including lists built to defeat it. Another line of work counts steps by the size of the target instead. Bellman's dynamic programming takes about n times t steps for target t. That is fast for small targets, but numbers with many digits allow enormous targets.

This paper claims to prove a worst-case time of O(2^(0.49n)). The O means at most a fixed constant times that amount. For 100 numbers, 2 to the power 49 is half of 2 to the power 50. For 1,000 numbers the saving is 2 to the power 10, a factor of 1,024. At that size, the 2023 factor n to the power 0.5023 is about 32. The new saving keeps doubling with every 100 extra numbers.

The algorithm is randomized: it makes random choices as it runs. On every input it gives the right answer with probability at least 2/3Source 3. Its time limit holds on every run, even a run that answers wronglySource 4. No assumption is made about how the input numbers were chosenSource 5. First, random tie-breaking weights make it likely that a solvable instance gets a version with exactly one solutionSource 6. Then the algorithm works with remainders after division by a large random prime. Matching only the remainder lets in impostors, which the paper calls aliases. An alias is a selection whose sum matches the target's remainder but not the target itselfSource 7.

Here lies the one hard step. The algorithm estimates a weighted total over all remainder matches. It then lists every alias and subtracts its shareSource 8. What remains is zero for an unsolvable instance and has size one for an isolated solutionSource 9. But both pieces of the subtraction can be far larger than one. So the estimate must be accurate to a small absolute error, not just in proportionSource 10. The paper builds a sampling estimate that meets this standard without checking every remainder.

The claim comes with conditions. The computer model is a word RAM, a machine that handles fixed-size blocks of bits in one step. Its blocks hold about 4(n + b) bitsSource 11. Here b is the bit length of the largest input number or target. The bound covers inputs whose bit length is at most a fixed power of n. It holds past some size N_c with some constant C_cSource 12. The theorem states that these exist but does not give their values in its statement. So it does not say how large n must be before the gain appears. A companion paper from September 2026 targets memory instead. It keeps time near 2 to the power n/2 and uses about 2 to the power n/5 wordsSource 13. Earlier memory records include Schroeppel and Shamir's 2^(n/4). In 2024, Belova, Chukhin, Kulikov and Mihajlin reached 2^(0.246n). Their bound needs input numbers below 2 to a fixed multiple of n.

How sure is this? No Lean formalization is listed for either paper. So no computer proof checker has checked these claims. No specialist review has been published yet.

What it doesn't show. This does not give a fast method. The time still doubles about every two extra numbers.