PICKING NUMBERS THAT ADD UP, ALMOST AS FAST AS READING THEM

Here is a puzzle anyone can state. You have a list of whole numbers — say 3, 9, 14, 20 — and a target, say 23. Can you pick some of them so that they add up exactly to the target? (Here, yes: 3 + 20 or 9 + 14.) This is Subset Sum, one of the most fundamental problems in computer science. The paper describes it as a fundamental NP-complete problem, a family of problems known for being hard to solve exactly.

There is a loophole, though. If the numbers are not too large, clever algorithms run in a time that depends on their size. The classic method, due to Bellman in 1957, takes time proportional to the count of numbers n times the target t. Since then, algorithms have kept improving:

Pisinger (1999): proportional to n × N, where N is the largest number;
Bringmann (2017): roughly n + t;
several teams (2021–2024): roughly n + N^(5/3), then n + N^(3/2).

The holy grail was time roughly n + N — not much more than reading the input. Researchers in the field had called it “the most crucial open problem” of this line of work.

Within a hair of the goal

Lin Chen, Yuchen Mao and Guochuan Zhang, of Zhejiang University in China, give an algorithm that runs in time n + N^(1+ε), where ε can be any small positive number fixed in advance — 0.1, 0.01, 0.001. It is deterministic, accepts negative numbers and repeated values, and comes with a mathematical proof. The authors call this time near-optimal.

The result extends to vectors: picking items so that several sums hit their targets at once, with time N^(d+ε) for d coordinates. That, in turn, answers part of a question raised by several groups about integer programming — finding whole-number solutions to systems of equations whose variables are bounded. Two consequences are worked out explicitly: splitting a set of numbers into two equal halves, and sharing jobs between two identical machines as evenly as possible.

Lifting numbers into a higher dimension

The key idea is geometric. It was already known that the problem is easy when the numbers are dense and the target lies well inside the range of possible sums. The authors’ observation: a sparse set of numbers can look dense when viewed in a higher dimension.

Their example is the set {11, 12, 22, 24}. Write 11 and 22 as one step and two steps along a first axis, and 12 and 24 as one step and two steps along a second axis. The possible sums then fill every point of a small 4-by-4 square. But squash that square back onto a line — by computing 11x + 12y — and the sums form seven separate clusters with gaps between them, scattered between 0 and 69. The gaps are an illusion of the projection; in two dimensions, the structure is simple.

The algorithm builds such higher-dimensional coordinates for any input, using results from additive combinatorics. Inside the “filled” region, answers come for free. Only a thin zone near the edge needs real work, which the algorithm breaks into smaller problems and solves recursively. Each round shrinks that zone sharply, and only a constant number of new dimensions is ever added.

How the proof was built

The paper opens with an “AI disclaimer”. The authors designed the main proof route themselves, building on their own recent work on dense, multidimensional versions of the problem. They then used an AI model, GPT Astra Ultra, to turn these ideas into complete mathematical proofs. It got stuck on several lemmas, which were resolved with ideas from the authors; a public research note documents the conversations. Once the basic randomised algorithm was done, the model extended it to the deterministic, multidimensional versions “without any guidance from the authors”. The model also drafted the paper and, the authors write, verified its main results with a proof in the Lean 4 proof assistant. The authors take full responsibility for the content.

Not quite the finish line

The exponent is 1 + ε rather than exactly 1, and the hidden constants grow as ε shrinks; the dependence on the number of dimensions is not optimised. The authors themselves describe the algorithm as “quite involved”. The paper is theoretical: it reports no implementation or benchmark.