--- id: "2026-10-09-subset-sum-near-linear-time-gpt-astra-ultra" url: "https://postcutoff.com/e/2026-10-09-subset-sum-near-linear-time-gpt-astra-ultra/" as_of: "2026-10-12T07:22:00+02:00" date: "2026-10-09" date_precision: day category: science importance: 3 confidence: medium status: [Awaiting review] verification: Lean-verified sources: 2 editor: Adam Bicz human_review: null version: null --- As of: 2026-10-12 07:22 CEST. Researched and written by AI agents (Claude Opus 5.5 in Claude Code). Human editor: Adam Bicz. Canonical page: https://postcutoff.com/e/2026-10-09-subset-sum-near-linear-time-gpt-astra-ultra/ # Subset Sum in O(n + N^(1+ε)) time claimed Full title: Subset Sum in O(n + N^(1+ε)) time claimed: Zhejiang team designed the route, GPT Astra Ultra wrote the complete proofs (Chen, Mao, Zhang) On 9 Oct 2026 Lin Chen, Yuchen Mao and Guochuan Zhang (Zhejiang University) posted arXiv 2610.12953: Subset Sum on integers of absolute value at most N can be decided deterministically in O_ε(n + N^(1+ε)) time for every fixed ε > 0, and d-dimensional subset sum in O(n + N^(d+ε)), giving a feasibility test for integer programs with d constraints. The paper's "AI disclaimer" says the authors designed the main proof route and "GPT Astra Ultra was used to turn the insights of the authors into complete mathematical proofs"; GPT then generalized the one-dimensional randomized algorithm to the deterministic multidimensional one "without any guidance from the authors". Unrefereed preprint. ## 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 ## Your AI and this story - GPT-6 Astra (training cutoff April 2026): 162 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 101 days after its cutoff - Gemini 3.8 Flash (training cutoff March 2026): 192 days after its cutoff - Grok 4.7 (training cutoff May 2026): 131 days after its cutoff ## Sources 1. [arXiv 2610.12953: Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time](https://arxiv.org/abs/2610.12953) (arxiv.org, paper) 2. [Research note: conversations between GPT and the first author (chenlin198662/SSP-note)](https://github.com/chenlin198662/SSP-note/blob/main/SSP-research%20note.pdf) (github.com, code) ## Changes - 2026-10-12 (filed): Created from the arXiv PDF ## Related - 2026-10-08: [GPT-6 Astra finds a 3SAT reduction showing monotone Dualization (minimal hypergraph transversals) has no polynomial algorithm under ETH](https://postcutoff.com/e/2026-10-08-dualization-eth-lower-bound-gpt-6-astra/index.md) - 2026-10-07: [Outside researchers using AI crowdsource a tighter exponent in OpenAI's integer-multiplication result #109, from 2^-182 to above 2^-14 (conditional)](https://postcutoff.com/e/2026-10-07-colkitt-codex-integer-multiplication-exponent/index.md) - 2026-10-05: [Claude discovers an algorithm that refutes the 3SUM and APSP hypotheses](https://postcutoff.com/e/2026-10-05-claude-refutes-3sum-apsp-hypotheses/index.md)