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

1 · The essentials

Subset Sum asks whether some of the integers in a list can add up to a given target. The main manuscript presents a method that uses random choices to answer this question. For a list of $n$ integers, it claims a running-time bound of $O (2^{0.49 n})$ , provided the number of bits needed to write each integer is bounded by a fixed polynomial in the list length. This time limit applies to every run, not just on average. On every allowed input, the method gives the correct answer with probability at least two-thirds. Repeated positive integers are allowed. A companion manuscript gives a different method with a stated limit on memory use as well as time. The main result has not been formalized in Lean or formally verified.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine choosing items with whole-number prices so that their total exactly matches a gift card's value. The claimed method is like a randomized way to answer whether such a selection exists, with a time limit on every attempt but a chance of answering incorrectly.

Why it matters

The main claim combines a running-time guarantee for every input and every run with a success guarantee for each input. The companion manuscript addresses memory use alongside time, giving a separate set of resource guarantees. Together, they describe two approaches to the same problem with different stated time and memory bounds.

2 · Going further

Subset Sum is the decision problem of determining whether a selection of the input integers sums to a target. The repository summary allows repeated positive integers. Here $n$ counts the input integers and $b$ denotes the maximum input bit length; the stated setting restricts input lengths to polynomially many bits and uses a word-RAM model with words of $O (n + b)$ bits.

The main manuscript claims a uniform randomized classical algorithm with ordinary worst-case running time $O (2^{0.49 n})$ . The bound holds on every random execution, while the probability of a correct answer is at least $2/3$ on every input. These are distinct guarantees: randomness can affect correctness, but does not create exceptions to the stated time bound. The supplied abstract does not describe the algorithm's internal construction or the argument establishing its bound, so no more specific mechanism can be explained from this source.

The companion manuscript claims a uniform classical randomized decision algorithm using $poly (n) 2^{n /2}$ time and ordinary $O (2^{n /5})$ writable words of $O (n + b)$ bits. These bounds hold on every execution under every fixed polynomial bound on input-integer bit length. Its error is one-sided: it always rejects unsolvable instances and accepts each solvable instance with probability at least $2/3$ . It therefore supplies a separate low-space result, rather than establishing that the main algorithm has this same memory bound.

Useful notions

Choosing a subset and adding its entries
Binary representation and bit length
Exponential and polynomial growth
Probability of a correct answer
Running time versus memory use

What was known before / what is new

Before

The supplied text identifies the subject as worst-case Subset Sum but gives no account of earlier algorithms or bounds. It does not name a prior benchmark or an earlier open problem, so a historical comparison cannot be made from this source alone.

New

The main manuscript presents a uniform randomized classical algorithm with ordinary $O (2^{0.49 n})$ time on polynomial-bit inputs, with the time bound holding on every execution. Its stated success probability is at least $2/3$ on every input. The companion manuscript presents a separate algorithm with explicit time and writable-memory bounds and one-sided error.

Limits and assumptions

The main running-time claim is restricted to polynomial-bit inputs in the stated word-RAM setting, with $n$ counting input integers and word size $O (n + b)$ bits. It is a randomized correctness guarantee, not a guarantee of a correct answer on every execution. The companion result applies under every fixed polynomial bound on input-integer bit length; its memory guarantee must not be transferred to the main algorithm. The main result is not formalized in Lean and has not been formally verified. The supplied abstracts omit the algorithmic constructions and arguments and identify no remaining open questions.

Mini glossary

Subset Sum: The problem of deciding whether a selection of input integers adds up to a given target.
Bit length: The number of binary digits needed to represent an integer.
Worst-case running time: A time bound that applies to every allowed input and, for these stated results, every random execution.
Word-RAM model: The computational setting used for the resource bounds, with words of $O (n + b)$ bits in the supplied summary.
One-sided error: For the companion algorithm, the guarantee that unsolvable instances are always rejected, while solvable instances may sometimes be rejected.

Keywords : Subset Sum · Randomized algorithms · Time–space bounds

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Gives a uniform randomized classical algorithm for worst-case Subset Sum in ordinary $O (2^{0.49 n})$ word-RAM time on polynomial-bit inputs, where n counts the integers. The time bound holds on every execution and success probability is at least 2/3 on every input. Inputs may repeat positive integers; words have $O (n + b)$ bits for maximum input bit length b.

To be verified: the proof is written in the manuscript, but no software has checked it and no validation by independent mathematicians is established. It may contain errors.

Manuscripts in this family

★

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

04/10/2026

To be verified

We give a uniform randomized classical algorithm for Subset Sum with bounded error and worst-case running time $O (2^{0.49 n})$ on polynomial-bit inputs in a word-RAM model, where n is the number of input integers. The time bound holds on every random execution.

PDF GitHub folder

A Low-Space Algorithm for Worst-Case Subset Sum

26/09/2026