Worst-case Subset Sum in time 2^((1/2 - c)n)

Given positive integers $a_1,\dots,a_n$ and a target $t$ , Subset Sum asks whether some subset of the $a_i$ sums to $t$ . The meet-in-the-middle algorithm of Horowitz and Sahni (1974) solves it in time $2^{n/2}\cdot\mathrm{poly}$ , and Schroeppel and Shamir (1981) kept that time with space $2^{n/4}$ . Later work saved only polynomial factors in the worst case (Chen, Jin, Randolph and Servedio, 2023, time $2^{n/2}/n^{\delta}$ ), while representation methods beat $2^{n/2}$ only on random instances. Is there an algorithm for worst-case $n$ -input Subset Sum running in time $2^{(1/2-c)n}$ for some constant $c>0$ ?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Exact exponential algorithms; fine-grained complexity
Posed by: Standing open question of exact exponential algorithms since Horowitz and Sahni (1974); stated as 'a major goal' by Chen, Jin, Randolph and Servedio (2023)
Year posed: —
Years open: —
Solved: 2026-10-04
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Unreviewed
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 46 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: a uniform randomized word-RAM algorithm decides Subset Sum with error at most 1/3 on every input and runs in worst-case time $O(2^{0.49n})$ for every fixed polynomial bound on input bit length, the time bound holding on every random execution. The method combines isolation, a random prime modulus, a filtered Fourier checksum and alias extraction. It is not deterministic, it does not treat super-polynomial bit lengths, and it does not improve the space bound. The companion manuscript separately gives one-sided error, time $\mathrm{poly}(n)2^{n/2}$ and space $O(2^{n/5})$ .

What the AI did

The release README says every result in it was produced by an unreleased internal OpenAI model following a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The principal manuscript is dated October 4, 2026; the low-space companion (September 26, 2026) is an earlier, separate result at the 2^(n/2) time scale.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the principal manuscript was read against the posed question. It gives a single uniform randomized algorithm, correct with probability at least 2/3 on every input, whose running time is at most $C_c 2^{0.49n}$ on every execution for inputs with bit length $b\le n^c$ , on a word RAM with $O(n+b)$ -bit words; the intermediate bound is $2^{0.489995n}\mathrm{poly}(n+b)$ . The model is stated precisely (no advice, no random oracle, randomness charged). Scope limits stated by the paper: randomized two-sided error (not deterministic), polynomial-bit inputs, word-RAM model. No Lean formalization exists for this family. The proof was not refereed.

Worst-case Subset Sum in time 2^((1/2 - c)n)

What was actually shown

What the AI did

Verification

Sources

Discussion