Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915575761993728 |
|---|---|
| author | Sajith, Thejas Radhika |
| author_facet | Sajith, Thejas Radhika |
| contents | Given a multiset $A = \{a_1, \dots, a_n\}$ of positive integers and a target integer $t$, the Subset Sum problem asks if there is a subset of $A$ that sums to $t$. Bellman's [1957] classical dynamic programming algorithm runs in $O(nt)$ time and $O(t)$ space. Since then, much work has been done to reduce both the time and space usage.
Notably, Bringmann [SODA 2017] uses a two-step color-coding technique to obtain a randomized algorithm that runs in $\tilde{O}(n+t)$ time and $\tilde{O}(t)$ space. Jin, Vyas and Williams [SODA 2021] build upon the algorithm given by Bringmann, using a clever algebraic trick first seen in Kane's Logspace algorithm, to obtain an $\tilde{O}(nt)$ time and $\tilde{O}(\log(nt))$ space randomized algorithm. A SETH-based lower-bound established by Abboud et al. [SODA 2019] shows that Bringmann's algorithm is likely to have near-optimal time complexity.
We build on the techniques used by Jin et al. to obtain a randomized algorithm running in $\tilde{O}(n+t)$ time and $\tilde{O}(n^2 + n \log^2 t)$ space, resulting in an algorithm with near-optimal runtime that also runs in polynomial space. We use a multipoint evaluation-based approach to speed up a bottleneck step in their algorithm.
We also provide a simple polynomial space deterministic algorithm that runs in $\tilde{O}(n^2t)$ time and $\tilde{O}(n \log^2 t)$ space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_04726 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space Sajith, Thejas Radhika Data Structures and Algorithms Computational Complexity Given a multiset $A = \{a_1, \dots, a_n\}$ of positive integers and a target integer $t$, the Subset Sum problem asks if there is a subset of $A$ that sums to $t$. Bellman's [1957] classical dynamic programming algorithm runs in $O(nt)$ time and $O(t)$ space. Since then, much work has been done to reduce both the time and space usage. Notably, Bringmann [SODA 2017] uses a two-step color-coding technique to obtain a randomized algorithm that runs in $\tilde{O}(n+t)$ time and $\tilde{O}(t)$ space. Jin, Vyas and Williams [SODA 2021] build upon the algorithm given by Bringmann, using a clever algebraic trick first seen in Kane's Logspace algorithm, to obtain an $\tilde{O}(nt)$ time and $\tilde{O}(\log(nt))$ space randomized algorithm. A SETH-based lower-bound established by Abboud et al. [SODA 2019] shows that Bringmann's algorithm is likely to have near-optimal time complexity. We build on the techniques used by Jin et al. to obtain a randomized algorithm running in $\tilde{O}(n+t)$ time and $\tilde{O}(n^2 + n \log^2 t)$ space, resulting in an algorithm with near-optimal runtime that also runs in polynomial space. We use a multipoint evaluation-based approach to speed up a bottleneck step in their algorithm. We also provide a simple polynomial space deterministic algorithm that runs in $\tilde{O}(n^2t)$ time and $\tilde{O}(n \log^2 t)$ space. |
| title | Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2508.04726 |