In the Subset Sum problem we are given a set of $n$ positive integers $X$ and a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural parameters for this problem that have been studied in the literature are $n$ and $t$ as well as the maximum input number $rm{mx}_X$ and the sum of all input numbers $Sigma_X$. In this paper we study the dense case of Subset Sum, where all these parameters are polynomial in $n$. In this regime, standard pseudo-polynomial algorithms solve Subset Sum in polynomial time $n^{O(1)}$. Our main question is: When can dense Subset Sum be solved in near-linear time $tilde{O}(n)$? We provide an essentially complete dichotomy by designing improved algorithms and proving conditional lower bounds, thereby determining essentially all settings of the parameters $n,t,rm{mx}_X,Sigma_X$ for which dense Subset Sum is in time $tilde{O}(n)$. For notational convenience we assume without loss of generality that $t ge rm{mx}_X$ (as larger numbers can be ignored) and $t le Sigma_X/2$ (using symmetry). Then our dichotomy reads as follows: - By reviving and improving an additive-combinatorics-based approach by Galil and Margalit [SICOMP91], we show that Subset Sum is in near-linear time $tilde{O}(n)$ if $t gg rm{mx}_X Sigma_X/n^2$. - We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with $t ll rm{mx}_X Sigma_X/n^2$, then the Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail. We also generalize our algorithm from sets to multi-sets, albeit with non-matching upper and lower bounds.
تحميل البحث