patternMinor
Using 4-SUM to improve Subset Sum $O(2^{n/2})$ runtime
Viewed 0 times
runtimeimproveusingsumsubset
Problem
I read k-Sum $k \geq 3$ can be solved in $\approx O(n^{k/2})$
If this is right, why do not have a subset sum solver with a time complexity $O(2^{n/4})$ or better?
That is, enumerating all the subsets from 4 splits, then apply 4-sum to find if some of the four partial lists add up to the target value?
If this is right, why do not have a subset sum solver with a time complexity $O(2^{n/4})$ or better?
That is, enumerating all the subsets from 4 splits, then apply 4-sum to find if some of the four partial lists add up to the target value?
Solution
Work through the math; you are off by a factor of two. Also, you might be confusing yourself by using the same letter $n$ for two different things.
Suppose we have a list of $N$ numbers. You are proposing to split that into four chunks, where each chunk has $N/4$ numbers. Enumerating all of the subsets of a single chunk takes $O(2^{N/4})$ time. Now, you have a 4-sum problem where you are working 4 lists each containing $M=2^{N/4}$ items. This 4-sum problem can be solved in $O(M^{k/2}) = O(M^{4/2}) = O(M^2)$, and $M^2 = 2^{N/2}$, so your proposed algorithm runs in $O(2^{N/2})$ time.
There is an algorithm for subset-sum that runs in time $O(2^{N/2})$ and space $O(2^{N/4})$. The algorithm is due to Schroeppel and Shamir. However, it's running time is still $O(2^{N/2})$, not $O(2^{N/4})$.
I don't think there is any known subset-sum algorithm whose running time is non-trivially better than $O(2^{N/2})$. Blum, Kalai, and Wasserman have solved a related problem in subexponential time, but it's a different problem.
Suppose we have a list of $N$ numbers. You are proposing to split that into four chunks, where each chunk has $N/4$ numbers. Enumerating all of the subsets of a single chunk takes $O(2^{N/4})$ time. Now, you have a 4-sum problem where you are working 4 lists each containing $M=2^{N/4}$ items. This 4-sum problem can be solved in $O(M^{k/2}) = O(M^{4/2}) = O(M^2)$, and $M^2 = 2^{N/2}$, so your proposed algorithm runs in $O(2^{N/2})$ time.
There is an algorithm for subset-sum that runs in time $O(2^{N/2})$ and space $O(2^{N/4})$. The algorithm is due to Schroeppel and Shamir. However, it's running time is still $O(2^{N/2})$, not $O(2^{N/4})$.
I don't think there is any known subset-sum algorithm whose running time is non-trivially better than $O(2^{N/2})$. Blum, Kalai, and Wasserman have solved a related problem in subexponential time, but it's a different problem.
Context
StackExchange Computer Science Q#97201, answer score: 4
Revisions (0)
No revisions yet.