Could Subset Sum Problem Be Solved In linear Time Using Logarithmic Space?

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?

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.

StackExchange Computer Science Q#74023, answer score: 5