Is there any known lower bound on the complexity of subset sum problem? For example, could it be solved in linear time using logarithmic space?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
No such bound is known; for all we know, it may be possible to solve it in linear time. In fact, for all we know, there might be an algorithm for it that uses $O(\log(n))$ space on its work tape.
We know one thing: There is not an algorithm which uses both linear time and logarithmic space. That is, there is a time-space lower bound! A Subset Sum instance of size $n$ can be reduced to a 3SAT instance of size $O(n^2)$ (perhaps there is a better reduction), and for 3SAT, we know that, if $t(t+s)<2$, then
$$3SAT \not\in TiSp\left(n^{t},n^{s}\right) $$
With $TiSp(t(n),s(n))$ the class of problems solvable in $O(t(n))$ time and $O(s(n))$ space. This is not the strictest bound, see Computational Complexity: A Modern Approach for more details.
But that still leaves open whether there is an algorithm which uses $O(n)$ time and $O(n)$ space. (Of course, the non-deterministic time hierarchy theorem tells us that for every $t(n)\in poly(n)$, there is a problem $L\in NP$ which provably requires $\Omega(t(n))$ time, the question is whether the subset sum problem is one of them.)
So yeah, that bound is not great. It's not the bound we deserve, but it is the bound we have right now.
answered Apr 16, 2017 at 9:28
-
$\begingroup$ First, the reduction should be from 3SAT, not to 3SAT. Second, if the reduction costs $O(n^2)$ then there's no guarantee that subset sum problem needs less than $O(n^2)$ time, and thus, this time-space lower bound (which is less than $O(n^2)$) does not hold in my opinion. Am I wrong? $\endgroup$ Commented Apr 17, 2017 at 18:00
-
$\begingroup$ @DudiFrid. You're absolutely right. The lower-bound still holds; the theorem is $NTime(n)\not\subseteq TiSp(n^t,n^s)$, but the proof as it stands now has elementary errors. I'll fix them, thanks! $\endgroup$ Commented Apr 17, 2017 at 18:19
-
1$\begingroup$ you still didn't fix the answer. Could you please do it? $\endgroup$ Commented Apr 22, 2017 at 12:40
-
1$\begingroup$ Would you like to fix the errors you've mentioned? $\endgroup$ Commented Apr 23, 2017 at 18:31