Subset Sum: a smaller time exponent and a separate low-memory algorithm

← All digests

Family 138 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Given positive integers $a_1,\ldots,a_n$ and a target $t$, does some subset add exactly to $t$? The statement fits in one sentence, but Subset Sum is a central NP-complete problem and a benchmark for exact exponential-time algorithms.

Trying all subsets takes roughly $2^n$ work. The classical meet-in-the-middle method splits the numbers in half, lists the subset sums of each half, and searches for complementary values. It brings the main exponential scale down to $2^{n/2}$.

Two questions motivate this family. Can a classical randomized algorithm improve the exponent below one half on every input? And how little memory can an algorithm use while retaining the half-exponential time scale?

The two manuscripts answer these separately. M1 claims worst-case $O(2^{0.49n})$ time for polynomial-bit inputs. M2 claims ordinary $O(2^{n/5})$ writable-word space with time polynomial times $2^{n/2}$. The family does not claim one algorithm simultaneously achieving both advertised bounds.

2. Background and essential definitions

A solution is an index set $I\subseteq\{1,\ldots,n\}$ satisfying

$$\sum_{i\in I}a_i=t.$$

Repeated input values are allowed, and the empty subset is permitted. Indices distinguish equal-valued items. Both manuscripts treat positive input integers and a nonnegative target.

Let $b$ be the maximum bit length of an input integer or the target. Their exponential guarantees apply under each fixed polynomial-bit convention $b\le n^c$, for a fixed positive integer $c$. The program does not receive $c$; constants and the threshold beyond which the resource bound applies may depend on it.

This is different from pseudopolynomial complexity. An algorithm polynomial in the numerical target $t$ can be extremely fast for small targets but exponential in the bit length of a large target. A polynomial bound on $b$ still permits enormous numerical values.

The stated machine is a word RAM with words of order $n+b$ bits. Arithmetic, comparisons, shifts, memory accesses, and fresh random words have specified unit costs on those words. Larger operations must be decomposed and charged. The input is read-only; retained randomness and all writable data count toward memory where a space bound is claimed.

A bounded-error algorithm may give a wrong answer with probability at most $1/3$ on each fixed input. A one-sided-error algorithm in this family never incorrectly answers YES, but may fail to find a solution that exists. Neither term means the inputs themselves are random.

3. Development history and previous partial results

Horowitz and Sahni’s meet-in-the-middle algorithm established the half-exponential time scale. Schroeppel and Shamir retained that scale while reducing space to roughly $2^{n/4}$: four smaller lists can generate the two large sum streams without storing them in full.

Recent worst-case improvements moved different parts of this frontier. Chen, Jin, Randolph, and Servedio obtained a polynomial-factor time saving below $2^{n/2}$ in specified RAM models. Dividing by a polynomial does not change the exponential rate from $1/2$, so it does not already yield $2^{0.49n}$.

Nederlof and Węgrzycki reduced the space exponent below one quarter, using representations and weighted disjointness. Belova, Chukhin, Kulikov, and Mihajlin improved it further to approximately 0.246 under their stated input-magnitude assumptions; see Improved Space Bounds for Subset Sum.

Representation methods originated in algorithms for random hard-knapsack instances, including work of Howgrave-Graham–Joux and Becker–Coron–Joux. They give a solution many decompositions, then filter the decompositions by modular conditions. Results for random inputs do not immediately imply a worst-case guarantee, because an adversarial instance may have very different collisions among partial sums.

A useful worst-case distinction is whether an input block has many or few distinct subset sums. Few distinct sums can be compressed and enumerated cheaply; many distinct sums can support plentiful filtered representations. Both new manuscripts exploit versions of that distinction while providing explicit resource caps.

4. What the new manuscripts claim

A time exponent below one half

M1 states that one uniform classical randomized decision algorithm is correct with probability at least $2/3$ on every input. For each fixed $c$, all sufficiently large inputs with $b\le n^c$ take at most

$$C_c\,2^{0.49n}$$

word operations on every execution, including executions that answer incorrectly. All preprocessing, tables, input accesses, and random sampling are charged.

The intermediate analysis gives $2^{0.489995n}\operatorname{poly}(n+b+2)$. The small strict slack below 0.49 absorbs that polynomial factor separately for each fixed polynomial-bit class. No separate low-space bound is attached to this theorem.

Less memory at the half-exponential time scale

M2 states that a uniform randomized algorithm never gives a false YES and succeeds on every YES instance with probability at least $2/3$. Under the same type of polynomial-bit convention, every run uses at most

$$A_c n^{k_c}2^{n/2}$$

operations and

$$A_c(n+b+2)^{15}2^{0.199n}$$

writable words. Consequently, for every fixed $\rho>0.199$, its ordinary space is $O_{c,\rho}(2^{\rho n})$; in particular, it is $O_c(2^{n/5})$.

At the endpoint 0.199, the polynomial factor remains. The cleaner exponent one fifth has enough slack to absorb it. Each word has $O(n+b)$ bits, so words should not be silently read as bits.

Both algorithms are finite uniform programs, with no input-size advice, externally supplied tables, random oracle, or free storage of previously used randomness. Their error probabilities concern arbitrary fixed instances, not a distributional promise.

5. Why the advance matters

Provisional importance: 4/5. A fixed improvement below the meet-in-the-middle exponent would be a major advance for a foundational exact-search problem. Exponential-rate savings eventually dominate polynomial-factor savings, even when the numerical change from 0.5 to 0.49 looks small.

The separate memory result addresses a different practical and theoretical bottleneck. Exponentially many stored sums can make an algorithm infeasible before its operation count becomes the limiting factor. Reducing the space exponent while maintaining the classical time scale enlarges the range of possible time–space tradeoffs.

These are still exponential-time algorithms, so the claims do not resolve $\mathrm P$ versus $\mathrm{NP}$. The word-RAM assumptions, polynomial-bit input regime, and asymptotic constants also matter before translating the bounds into concrete performance estimates.

The rating reflects worst-case improvements in two central resource measures. It does not combine the manuscripts into an unsupported simultaneous time-and-space guarantee or imply an immediate cryptanalytic impact for every structured instance family.

6. The main idea

Detect an isolated solution through a corrected checksum

M1 first adds small random tie-breaking weights. An isolation argument ensures that, with high constant probability, one of polynomially many transformed targets has exactly one solution whenever the original instance is solvable.

Choose a random prime modulus and assign a complex phase to each subset. The exact-solution checksum can be written as

$$\sum_{\text{exact solutions}}\chi(I) = \sum_{\text{modular solutions}}\chi(I) - \sum_{\text{modular aliases}}\chi(I).$$

An alias has the correct sum modulo the prime but the wrong integer sum. On a negative instance the left side is zero; at an isolated positive target it is one phase of absolute value one.

The modular sum is expressed by Fourier inversion, but the modulus is too large to scan all frequencies. M1 splits frequency indices into high and low digits and filters two corresponding lists using random phase information. Some groups are summed directly; others are sampled with an inverse-coverage correction so that frequencies appearing in several matches are not overcounted.

The required estimate has small absolute error. A relative estimate of a potentially huge modular sum would not suffice when two large quantities must cancel to leave zero or a unit-size answer.

A separate representation procedure lists the aliases. The construction avoids enumerating pairs satisfying the exact integer equation, so random-prime collision estimates apply to nonzero discrepancies. Combining alias subtraction with the checksum distinguishes the isolated case from the empty one. Finite-precision calculations and capped loops are included in the stated all-execution bound.

Compress collisions or exploit many representations

M2 runs two trials rather than trying to determine in advance which kind of instance it has. One chooses several disjoint blocks and compresses repeated subset sums. Sorted streams combine these lists without storing full Cartesian products, and modular buckets are processed one at a time.

The other trial gives a solution many decompositions across shared coordinate blocks. Records retain both an exact weight and a mask identifying selected shared indices. Equal weights with different masks cannot be merged indiscriminately, because they may have different compatibility with another record.

Nested modular filters reduce the candidate lists. An additional prime splits them into smaller buckets, while disjointness tests ensure that a combined representation does not use an item twice. Random separating sets reduce compatible-mask searches to exact two-sum checks.

Memory caps require careful handling of overflow. Some oversized buckets are skipped; others are subdivided by fixing successive mask bits and regenerated. Restrictions are imposed before joining the leaf lists, allowing repeated work to be charged to refinement depth. This controls raw tuple generation, not merely the number of distinct stored records.

The success analysis fixes a useful representation before exposing later randomness. The resource analysis bounds overflow and operation failures without conditioning on that rare successful representation. Independent repetitions then raise success to the stated constant while respecting the caps on every run.

7. Scope, limitations, and open questions

M1 is a decision algorithm with bounded error; M2 has the stronger one-sided-error convention but a different time bound. Neither main statement here is a deterministic algorithm, and the digest does not add a witness-output guarantee that the statements do not advertise.

The polynomial-bit convention is essential for absorbing polynomial factors into the displayed exponent slack. If $b$ grows faster, the same clean asymptotic expressions need not follow. Unit-cost operations also apply only to the specified word size.

The low-space theorem counts every writable register, stack, seed, and retained random value. Reusing random bits without storing them is not free. The time theorem similarly includes preparation rather than assuming precomputed input-dependent tables.

Sharper exponents, deterministic worst-case improvements, and algorithms combining the two resource savings remain natural questions. Practical crossover and behavior on cryptographic distributions require separate analysis. The checksum, filtering, and memory-accounting arguments are reported as manuscript claims rather than independently verified.

8. Sources and further reading

The linked time-improvement and space-improvement papers show the immediate earlier frontier. The source manuscripts’ bibliographies give the classical Horowitz–Sahni and Schroeppel–Shamir algorithms and the representation-method origins. M1 below supplies the 0.49 time claim; M2 supplies the one-sided low-memory claim.

Source manuscripts

• M1. OpenAI, Subset Sum in Time $O(2^{0.49n})$ (October 4, 2026).
• M2. OpenAI, A Low-Space Algorithm for Worst-Case Subset Sum (September 26, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.