4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\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$ – Dudi Frid Apr 17 '17 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$ – Lieuwe Vinkhuijzen Apr 17 '17 at 18:19
  • 1
    $\begingroup$ you still didn't fix the answer. Could you please do it? $\endgroup$ – Dudi Frid Apr 22 '17 at 12:40
  • 1
    $\begingroup$ Would you like to fix the errors you've mentioned? $\endgroup$ – Dudi Frid Apr 23 '17 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.