Subset Sum in O(n + N^(1+ε)) time claimed
Zhejiang team designed the route, GPT Astra Ultra wrote the complete proofs (Chen, Mao, Zhang)
Awaiting review
The takeaway
A long-open question in algorithms, whether Subset Sum can be solved in time near-linear in the largest input number, gets a claimed positive answer. The authors designed the approach; GPT Astra Ultra turned it into a 105-page paper and generalized it without guidance.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- 3 of 5
- Last verified
- 12 October 2026
Your AI and this story
- GPT-6 Astra162 days after its cutoff
- Claude Opus 5.5101 days after its cutoff
- Gemini 3.8 Flash192 days after its cutoff
- Grok 4.7131 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 101 days before it.
Key facts
- Paper: ‘Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time’, arXiv 2610.12953 [cs.DS], 9 Oct 2026; Lin Chen, Yuchen Mao, Guochuan Zhang (Zhejiang University); 105 pages
- Abstract: ‘A long open problem is whether Subset Sum can be solved in O(N) time. We show that Subset Sum can be solved in O(N^(1+ε)) time where ε > 0 is an arbitrarily small constant.’
- Corollary 1.2: subset sum for an explicitly listed multiset in [−N, N] ‘can be decided deterministically in O_ε(n + N^(1+ε)) word-RAM time, with unrestricted multiplicities’. Theorem 1.1 gives O_{d,ε}(n + N^(d+ε)) for vectors in dimension d
- Earlier target-independent bounds in the paper’s table: Õ(n + N^(5/3)) (Polak–Rohwedder–Węgrzycki 2021) and Õ(n + N^(3/2)) (Chen–Lian–Mao–Zhang 2024; Jin 2023); Bringmann’s 2017 algorithm runs in Õ(n + t), where the target t can be as large as nN
- Idea (abstract): dense inputs with the target inside the zonotope were already known to be easy. ‘Our key observation is that a sparse input can exhibit a dense structure when lifted to higher dimension’; the thin region near the zonotope’s boundary is split into subproblems and solved recursively
- AI disclaimer: ‘The main proof route for 1D subset sum was designed by the authors … GPT Astra Ultra was used to turn the insights of the authors into complete mathematical proofs. During the proof, GPT encounters trouble in proving several lemmas, which was eventually resolved by taking ideas from the authors.’
- AI disclaimer, continued: ‘After obtaining the randomized near-linear time algorithm for 1D subset sum, GPT was able to generalize it directly to deterministic algorithms for multidimensional multiset without any guidance from the authors. GPT was used for drafting the paper. GPT also verified this papers main results using the Lean 4 proof.’ A research note with the conversations is linked (github.com/chenlin198662/SSP-note)
- Caveats: the Lean proof is described as produced by GPT and is not linked from the abstract page; no independent check or expert reaction was found as of 12 Oct 2026
What happened
Subset Sum asks whether some of n given integers add up to a target. It is NP-complete, but it can be solved in time polynomial in the size of the numbers. A long line of work asked how small the dependence on the largest number N can be, with exponents falling from 2 to 5/3 to 3/2. Chen, Mao and Zhang, who wrote several of those earlier papers, now claim an exponent arbitrarily close to 1, which is essentially optimal, and extend it to several dimensions and to integer programs with a fixed number of constraints.
The paper is explicit about the division of labour. The authors supplied the structure of the argument. GPT Astra Ultra wrote out the proofs, got stuck on several lemmas that the authors resolved, and then generalized the algorithm to the deterministic, multidimensional, multiset case on its own. The conversations are published as a research note.
Why it matters
It is a central problem of pseudopolynomial algorithms, claimed by a group with a track record on it. It also shows a working pattern that is becoming common in theoretical computer science: experts provide the plan, a model produces a very long, detailed proof. A 105-page AI-written proof is hard for referees to check, so the claim should be treated as open until others verify it.
What is disputed or not yet verified
| Verification | Unrefereed preprint; authors report a Lean 4 verification made by GPT; not independently checked |
|---|
Sources
2 sources from 2 sites. Numbers match the chips in the text.
2 sources: 2 primary
Primary
Changes
- Filed from the arXiv PDF