Source-linked AI summary
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
Karl Bringmann
TL;DR
Subset Sum asks whether a subset of positive integers reaches a target, with the classic dynamic program taking O(nt) time. This paper gives a randomized O~(n + t)-time algorithm and improves polynomial-space bounds, with the strongest stated time bound relying on ERH.
Problem
The classic dynamic program takes O(nt) time, and the paper addresses whether Subset Sum can be solved faster while using polynomial space.
Source: §1 · pp. 2–3Method
The paper combines a randomized near-linear-time Subset Sum algorithm with additional techniques for polynomial-space computation.
Source: §6 · p. 16Results
The randomized Subset Sum algorithm runs in O~(n + t) time; polynomial-space bounds are O~(nt) time and O~(n log t) space with ERH, and O~(n t^(1+ε)) time and O~(n t^ε) space unconditionally.
Source: §6 · p. 16Takeaways & Limitations
The O~(n + t)-time algorithm matches conditional lower bounds, while the improved polynomial-space bounds still leave an O~(n + t)-time, O~(n log t)-space algorithm open.
Source: §1 · p. 3, §6 · p. 16An O~(n + t)-time algorithm using O~(n log t) space remains an open problem.
Source: §1 · p. 3
Abstract
from arXiv · showhide
Given a set $Z$ of $n$ positive integers and a target value $t$, the Subset Sum problem asks whether any subset of $Z$ sums to $t$. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves Subset Sum in time $O(nt)$. This has been improved to $O(n \max Z)$ by Pisinger [J. Algorithms'99] and recently to $\tilde O(\sqrt{n} t)$ by Koiliaris and Xu [SODA'17]. Here we present a simple randomized algorithm running in time $\tilde O(n+t)$. This improves upon a classic algorithm and is likely to be near-optimal, since it matches conditional lower bounds from Set Cover and k-Clique. We then use our new algorithm and additional tricks to improve the best known polynomial space solution from time $\tilde O(n^3 t)$ and space $\tilde O(n^2)$ to time $\tilde O(nt)$ and space $\tilde O(n \log t)$, assuming the Extended Riemann Hypothesis. Unconditionally, we obtain time $\tilde O(n t^{1+\varepsilon})$ and space $\tilde O(n t^\varepsilon)$ for any constant $\varepsilon > 0$.
1 Introduction
The introduction presents a randomized near-linear-time Subset Sum algorithm and improved polynomial-space bounds, alongside techniques for computing sums and context on related work.
1 Introduction
- Time O~(n + t) gives a randomized, one-sided-error Subset Sum algorithm and matches conditional lower bounds from Set Cover and combinatorial k-Clique.The error probability is (n + t)^−Ω(1).Source: §1 · p. 2
- UnboundedSubsetSum, where each input number may be used multiple times, has a deterministic O~(n + t) algorithm.The stated bound in Theorem 1.2 is O(n + t log t).Source: §1 · p. 3
- With ERH, the polynomial-space algorithm runs in time O~(nt) and space O~(n log t); unconditionally, it runs in time O~(n t^(1+ε)) and space O~(n t^ε).The earlier polynomial-space bounds were O~(n^3t) time and O~(n^2) space; achieving O~(n + t) time with O~(n log t) space remains open.Source: §1 · p. 3
1.1 Techniques
- Color-coding finds sums from small subsets, while layer splitting and a two-stage partition reduce the overhead to obtain O~(n + t) time.The method combines layer sumsets using t-capped sumset computations, which can be implemented in O(t log t) time.Source: §1.1 · pp. 3–4, Layer Splitting · p. 4
1.2 Further Related Work
- Prior work includes pseudopolynomial algorithms for structured dense instances and approximation algorithms; the best stated approximation runtime is O~(min{n/ε, n + 1/ε^2}).The passage notes a near-linear algorithm for a dense case when t is much smaller than n^2.Source: §1.2 · p. 5
2 Preliminaries
The preliminaries define bounded subset sums and the sumset operations used to compute them. They also describe how multiset inputs can be reduced to instances with bounded multiplicities.
Sums and Sumsets
- S(Z; t) is the set of subset sums at most t, and the t-capped sumset keeps sums at most t while allowing at most one element from each input set.The paper denotes the sum of a set S by Σ(S).Source: §2 · p. 5
Sumset Computation
- Boolean convolution of characteristic vectors computes a sumset, and integer multiplication gives an O(t log t) time bound for t-capped sumsets.The multiplication-based convolution bound is stated for the RAM model with cell size w = Θ(log t).Source: §2 · pp. 5–6
Preprocessing Multisets
- A multiset can be converted to an equivalent instance with multiplicities at most 2 by replacing repeated copies of an integer with copies of its double.The conversion takes O(n + t) time and yields an instance of size at most min{n, 2t}.Source: §2 · p. 6
- The paper applies this preprocessing so its algorithms can assume the input is a set contained in {0, . . . , t}.Koiliaris and Xu's alternative preprocessing computes whole subset-sum sets for two parts, which the paper says is irrelevant to its algorithms.Source: §2 · p. 6
3 Near-Linear Time Algorithm
The section presents a randomized algorithm that computes all subset sums bounded by t, using color-coding for small subsets and layer splitting for the full instance. It combines the layers to obtain a near-linear-time algorithm.
3.1 Color-Coding: An algorithm for small solution size
- Randomly partitioning the input into k^2 sets lets their capped sumset contain sums from subsets of size at most k when each such subset is split across the sets.Repeating the partitioning yields success probability at least 1 − δ; the resulting algorithm runs in O(tk^2 log t log(1/δ)) time.Source: §3.1 · p. 7
3 Near-Linear Time Algorithm
- O(t log t log^3(n/δ) log n) time suffices to compute a set containing every subset sum at most t with probability at least 1 − δ.The algorithm splits the input into O(log n) layers and combines their computed sumsets.Source: §3.2 · p. 8
3.2 Layer Splitting
- For an ℓ-layer instance, ColorCodingLayer computes a set containing every subset sum at most t with probability at least 1 − δ in O(t log t log^3(ℓ/δ)) time.It partitions the layer into about ℓ/log(ℓ/δ) parts and applies ColorCoding to each part before combining their sumsets in a tree.Source: §3.2 · pp. 8–9
4 Polynomial Space Algorithm
This section develops polynomial-space Subset Sum algorithms by converting FasterSubsetSum into a probabilistic arithmetic circuit evaluated with modular arithmetic, using prime selection and root-of-unity computation. It analyzes prime sampling for domain reduction, including an ERH-dependent threshold and a sampling-time bound without that assumption.
4.1 Setup
- A modular-arithmetic version of Lokshtanov and Nederlof’s circuit evaluation computes an output coordinate in time O~(|C|t log p) and space O(|C| log p).It assumes singleton constants, no overflowing convolution gates, and a t-th root of unity in Z_p.Source: §4.1 · p. 11
4.2 FasterSubsetSum as a Circuit
- A probabilistic circuit of size O~(n) and vector length t′ = O(t log^3 n) represents FasterSubsetSum, with no false positives and false-negative probability at most 1/n.The circuit can be sampled in O~(n) time, and each gate’s entry sum is bounded by 2 O~(n).Source: §4.2 · pp. 11–12
4.3 Reducing the Domain Size
- A random prime from a sufficiently large set preserves zero outputs for non-solutions and gives solutions output zero with probability O~(1/n); a random-element procedure finds a primitive τ-th root in expected polylogarithmic time.The prime set’s maximum size is τ^O(1) under ERH and at most O(exp(τ^ε)) unconditionally.Source: §4.3 · pp. 13–14
- Under ERH, the algorithm solves Subset Sum in time O~(nt) and space O~(n log t); unconditionally, it achieves time O~(nt^(1+ε)) and space O~(nt^ε).These bounds follow by choosing primes with a τ-th root of unity and controlling their maximum size.Source: §4.3 · p. 14
- For x = n^2 + exp(τε) = O(exp(τε)), |P| = ˜Ω(n^2), and sampling a prime from P takes τ^O(ε) time.Halting after essentially the expected number of repetitions gives a worst-case bound with error probability at most 1/τ; the log-factor count depends on ε and is not explicit because Siegel-Walfisz constants are ineffective.Source: §4.3 · p. 15
- Under the Extended Riemann Hypothesis, x = ˜O(τ(τ + n^2)) suffices for R to contain ˜Ω(n^2) primes, with random sampling taking expected O(polylog(τ)) time [8, Proposition 4.3].The threshold includes sufficiently many hidden logarithmic factors.Source: §4.3 · p. 15
5 Unbounded Subset Sum
The unbounded variant allows each input number to be used any number of times, and the paper gives a ˜O(t)-time algorithm that computes which targets up to t are attainable. Its staged sumset computation builds on dynamic programming and differs from the bounded problem, where repeated use of an item is not allowed.
5 Unbounded Subset Sum
- Unbounded Subset Sum allows each input number to be chosen arbitrarily often, unlike the bounded variant, and necessarily has n ≤ t.The task is to decide whether a sequence over Z sums to exactly t.Source: §5 · p. 15
- The algorithm computes attainability for every target up to t in ˜O(t) time, more precisely O(t log t).It returns the set of sums attainable by sequences over Z, including the empty sequence.Source: §5 · pp. 15–16
- The algorithm first computes sums up to t/n by classic dynamic programming in O(t) time, then extends the covered range through successive sumset computations.The initial set is S0 := Sunb(Z; t/n).Source: §5 · p. 16
- For a sequence whose sum exceeds the previous range, splitting at the first crossing item expresses its sum using two prior-range sums and one input number.This yields the inductive correctness argument for the sumset update; the same reuse of numbers is unavailable in bounded Subset Sum, where even Z ⊕t Z may include z + z.Source: §5 · pp. 15–16
6 Conclusion
The paper presents a randomized ˜O(n+t)-time Subset Sum algorithm using color-coding to find small solutions and split large ones. It also improves polynomial-space bounds, while matching conditional lower bounds and leaving a faster polynomial-space combination open.
6 Conclusion
- The randomized algorithm runs in ˜O(n+t), improving the classic O(nt) algorithm and matching conditional lower bounds from Set Cover and k-Clique.It has one-sided error and uses color-coding for small solutions and a two-stage color-coding-like process to split large solutions.Source: §6 · p. 16
- For SubsetSum on n positive numbers with target t, the randomized algorithm runs in ˜O(n + t) time with one-sided error, improving on the textbook O(nt) algorithm.Source: §6 · p. 16
- Polynomial-space bounds improve to ˜O(nt) time and ˜O(n) space under ERH, or ˜O(n t^(1+ε)) time and ˜O(n t^ε) space unconditionally.Obtaining ˜O(n+t) time with ˜O(n) space remains open.Source: §6 · p. 16