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

> A randomized algorithm claims to decide every Subset Sum instance in O(2^(0.49n)) time, below the 2^(n/2) scale. Plain-English explainer with sources.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-138/
Last updated: 2026-10-11

**A randomized algorithm claims to decide every Subset Sum instance in O(2^(0.49n)) time, below the 2^(n/2) scale.**

**Trust:** Claimed, not checked · **Papers:** 2 · **First paper:** September 26, 2026 · **Field:** Theoretical computer science · **Entry:** 138

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

Subset Sum asks whether some of n given whole numbers add up exactly to a target. A classic 1974 method needs about 2 to the power n/2 steps. A 2023 gain cut the time only by a factor that grows like a power of n. This paper claims to prove a randomized method that needs at most a constant times 2 to the power 0.49n. It is right with probability at least 2/3 on every input, and its time limit holds on every run.

## At a glance

- **First step:** 1974 (Horowitz and Sahni, meet-in-the-middle method, which the paper credits with the familiar 2^(n/2) time scale)
- **Significance:** Major. It claims a fixed cut in the worst-case time exponent. The earlier gains it cites saved only polynomial factors.
- **Trust:** Claimed, not checked
- **Field:** Theoretical computer science (2 papers)

**Worst-case time exponent for Subset Sum**

| Year | Who | Value |
| --- | --- | --- |
| 1974 | Horowitz and Sahni | 0.5 |
| 2023 | Chen, Jin, Randolph and Servedio | 0.5 |
| 2026 | This paper | 0.49 (this result) |

Time grows like 2 to the power (exponent × n). Smaller is better. The 2023 result kept 0.5 and saved a polynomial factor.

## 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 objective[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 input[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/3[3]. Its time limit holds on every run, even a run that answers wrongly[4]. No assumption is made about how the input numbers were chosen[5]. First, random tie-breaking weights make it likely that a solvable instance gets a version with exactly one solution[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 itself[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 share[8]. What remains is zero for an unsolvable instance and has size one for an isolated solution[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 proportion[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) bits[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_c[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 words[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.

## Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

## Hype check

Major if the proof holds, but it is a claim. No Lean formalization is listed and no specialist review is published. The gain is in theory only: the constants are unstated and the time still grows exponentially.

## Words used

- **Subset Sum:** The puzzle of deciding whether some of a list of whole numbers add up exactly to a target.
- **NP-complete:** A large family of problems that no one knows how to solve quickly, all convertible into one another.
- **Worst case:** A guarantee that holds for every possible input, not just typical or random ones.
- **Randomized algorithm:** A method that makes random choices as it runs and may err with a small, bounded chance.
- **Polynomial factor:** A saving that grows like a fixed power of n, such as n squared, much slower than any change in the exponent.
- **O notation:** O(f) means at most a fixed constant times f, once the input is large enough.
- **Word RAM:** A model computer that reads, writes and does arithmetic on fixed-size blocks of bits in one step each.
- **Alias:** A selection whose sum matches the target after division by the chosen prime, but not exactly.

## The original papers (2)

- [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf) - October 4, 2026
- [A Low-Space Algorithm for Worst-Case Subset Sum](https://github.com/openai/math/blob/main/preprints/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026/paper.pdf) - September 26, 2026

## Quoted lines from the paper (13)

[1] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> A fixed reduction of the exponential rate below $1/2$ is a different objective from such polynomial-factor savings.

[2] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> Their improvements concern random instances, not a guarantee for every input.

[3] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> For every input with $n\ge2$, the algorithm halts on every execution and outputs the correct answer with probability at least $2/3$.

[4] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> The running-time bound applies even to executions on which the answer is incorrect.

[5] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> In particular, no distributional assumption is made on the input integers.

[6] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> The isolation lemma of Mulmuley, Vazirani, and Vazirani ensures that, with high constant probability, some transformed target has exactly one solution whenever the original instance is positive.

[7] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> For each transformed target $t'$, a subset is an \emph{alias} if its sum is $t'$ modulo $P$ but not over the integers.

[8] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> We estimate the modular sum and subtract the phases of a complete list of aliases.

[9] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> On a negative instance the left side is zero for every transformed target; an isolated positive target leaves a single phase of modulus one.

[10] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> The two sums on the right can be much larger, so their difference must be recovered to small \emph{absolute} error.

[11] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> The machine is a word RAM with word length \begin{equation} w=\left\lceil4\bigl(n+b+\log_2(n+2)\bigr)\right\rceil. \end{equation}

[12] From [Subset Sum in Time O(2^(0.49n))](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf):

> For every fixed positive integer $c$, there are constants $C_c>0$ and $N_c\ge2$ such that every input with $n\ge N_c$ and $b\le n^c$ is processed, on every outcome of the random choices, in at most \[ C_c\,2^{0.49n} \] word operations.

[13] From [A Low-Space Algorithm for Worst-Case Subset Sum](https://github.com/openai/math/blob/main/preprints/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026/paper.pdf):

> We give a uniform algorithm with ordinary $O(2^{n/5})$ working space under each fixed polynomial bound on the input-integer bit length.

## Other sources

- [E. Horowitz and S. Sahni, “Computing Partitions with Applications to the Knapsack Problem”, Journal of the ACM 21 (1974), 277–292](https://doi.org/10.1145/321812.321823)
- [R. Schroeppel and A. Shamir, “A T=O(2^{n/2}), S=O(2^{n/4}) Algorithm for Certain NP-Complete Problems”, SIAM Journal on Computing 10 (1981), 456–464](https://doi.org/10.1137/0210033)
- [X. Chen, Y. Jin, T. Randolph and R. A. Servedio, “Subset Sum in Time 2^{n/2}/poly(n)”, APPROX/RANDOM 2023, LIPIcs 275, 39:1–39:18](https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.39)
- [R. M. Karp, “Reducibility among Combinatorial Problems”, in Complexity of Computer Computations, Plenum Press (1972), 85–103](https://doi.org/10.1007/978-1-4684-2001-2_9)
- [OpenAI, “Subset Sum in Time O(2^{0.49n})”, openai/math release preprint (October 4, 2026)](https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf): “We give a uniform randomized classical algorithm for Subset Sum with bounded error and worst-case running time $O(2^{0.49n})$ on polynomial-bit inputs in a word-RAM model, where $n$ is the number of input integers.”
- [T. Belova, N. Chukhin, A. S. Kulikov and I. Mihajlin, “Improved Space Bounds for Subset Sum”, ESA 2024, LIPIcs 308, 21:1–21:17](https://doi.org/10.4230/LIPIcs.ESA.2024.21)

## Related

- [Deterministic polynomial factorization over prime fields](https://closedform.nishachay.tech/e/openai-math-2026-142/) - Theoretical computer science
- [Exponential state costs for two-way automata](https://closedform.nishachay.tech/e/openai-math-2026-129/) - Theoretical computer science
- [Polynomial-time scheduling on three identical machines](https://closedform.nishachay.tech/e/openai-math-2026-124/) - Theoretical computer science
- [Almost-linear approximation of edit distance](https://closedform.nishachay.tech/e/openai-math-2026-121/) - Theoretical computer science
- [Exact derandomization of logarithmic space: L=RL=BPL](https://closedform.nishachay.tech/e/openai-math-2026-103/) - Theoretical computer science
- [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 40 results
- [Open since the 1970s](https://closedform.nishachay.tech/open-since/1970s/) - Era · 63 results
- [Claimed, not yet checked](https://closedform.nishachay.tech/trust/claimed/) - Trust · 130 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20138%5D%20)