Fast Low-Space Algorithms for Subset Sum
share
We consider the canonical Subset Sum problem: given a list of positive integers a_1,…,a_n and a target integer t with t > a_i for all i, determine if there is an S ⊆ [n] such that ∑_i ∈ S a_i = t. The well-known pseudopolynomial-time dynamic programming algorithm [Bellman, 1957] solves Subset Sum in O(nt) time, while requiring Ω(t) space. In this paper we present algorithms for Subset Sum with Õ(nt) running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in Õ(nt) time and O(log(nt)) space with access to O(log n loglog n+log t) random bits. This significantly improves upon the Õ(n t^1+ε)-time, Õ(nlog t)-space algorithm of Bringmann (SODA 2017). We also give an Õ(n^1+εt)-time, O(log(nt))-space randomized algorithm, improving upon previous (nt)^O(1)-time O(log(nt))-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a polylog(nt)-space, Õ(n^2 t)-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter 1≤ k≤min{n,t}, we present a randomized algorithm running in Õ((n+t)· k) time and O((t/k) polylog (nt)) space. As an application of our results, we give an Õ(min{n^2/ε, n/ε^2})-time and polylog(nt)-space algorithm for "weak" ε-approximations of Subset Sum.
READ FULL TEXT