12
$\begingroup$

I'm wondering what is known about the relation between time and memory for polynomial-time algorithms (which are necessarily also polynomial-space). In particular, I would like to learn what is known about less time vs. less memory, in the following sense:

Is it known whether (say) any language $L$ recognized by a polynomial-time algorithm $A$ which is polynomial-space $O(n^s)$ ($s>2$ say), can also be recognized by a polynomial-time algorithm $B$ which is polynomial-space $O(n^{s/2})$? Presumably any $B$ with less memory would need significantly more time, but can we restrict this extra time to polynomial-time?

So, recapping: is there for poly-time algorithms, some general way to compensate for less memory, in polynomial time? Answers and references greatly appreciated.

update: Dan Brumleve and Timothy Chow have given valuable insights and references in the comments and in this chat. It seems that time-space trade-offs like the one in this question are still a bridge too far.

$\endgroup$
  • 2
    $\begingroup$ Surely the answer to this is 'no', because some problems have, say, $\Omega(n^3)$ lower bounds on their time complexity regardless of space usage? $\endgroup$ – LSpice Jan 9 '18 at 20:46
  • 2
    $\begingroup$ The compensating algorithm gets more time, not less. So your remark doesn't immediately help me see why a memory-rich polytime algorithm cannot be mimicked by a less memory-rich but time-richer polytime algorithm. Or am I missing something obvious? $\endgroup$ – Frank'a Waaldijk Jan 9 '18 at 21:29
  • 1
    $\begingroup$ Don't worry, I'm also quite good in misreading :-) and I'm sure your remark helps other people to understand the question better. $\endgroup$ – Frank'a Waaldijk Jan 10 '18 at 0:12
  • 3
    $\begingroup$ Nothing like this is known for general computations, although I'm not sure I could back up this claim with a reference since it's so far beyond the current frontier of knowledge that people don't usually discuss it. A useful keyword for you may be DTISP, which is used for complexity classes that are simultaneously time-bounded and space-bounded. $\endgroup$ – Timothy Chow Jan 11 '18 at 19:33
  • 2
    $\begingroup$ Another observation which supports Timothy Chow's claim that this problem is hard: if we had $\text{DTISP}(n^a, n^b) = \text{DTISP}(n^{2 \cdot a}, n^{\frac{b}{2}})$ for all $a, b$ in some model, by iterating it we would obtain that for all $\epsilon > 0$, $\text{P} \subseteq \text{DTISP}(n^{O(1)}, n^{\epsilon})$. That is really close to $\text{P} \subseteq \text{DTISP}(n^{O(1)}, n^{o(1)})$ which implies $\text{P} \neq \text{PSPACE}$. $\endgroup$ – Dan Brumleve Jan 13 '18 at 5:24
10
$\begingroup$

It is an open problem whether or not every polynomial time algorithm can be made $O(\log(n))$-space. Note that every $O(\log(n))$-space algorithm is simultaneously polynomial time because it has $2^{O(\log(n))} = n^{O(1)}$ states. This problem is usually referred to as $\text{P} = \text{L}$. Amazingly, $\text{NP} = \text{L}$ is also open!

If we want to talk about particular algorithms and polynomial exponents, we'll also want to get specific about the model of computation. For example, consider the class of models of computation related to a Turing machine by time translations satisfying $T_b \in T_a \cdot S_a^{O(1)}$ and space translations satisfying $S_b \in O(S_a)$. This includes single-tape and multi-tape Turing machines and variations of $\text{RAM}$. We can't say much, since an algorithm with $T_a = S_a$ in one model can have $T_b = S_b^{O(1)}$ in the other, that is, by changing the model an algorithm can be made arbitrarily more space-efficient relative to the time it takes.

I posed a related problem recently over on cstheory.SE.

$\endgroup$
  • $\begingroup$ thanks for your answer Dan, I will have to ponder this. but now I first need some sleep :-), I will get back to you, cheers Frank $\endgroup$ – Frank'a Waaldijk Jan 10 '18 at 0:15
  • $\begingroup$ OK I have given it some thought, hopefully enough to comment sensibly. Your answer addresses a stronger question, the flavor of which is indeed very close to what I'm looking for. But to go from polynomial space $S_a\in O(n^{s})$ to $S_{a'}\in O(\log(n))$ seems far stronger than to go from $S_a\in O(n^{s})$ to $S_{a'}\in O(n^{s/2})$, especially if we specify $s>2$. That P = L is still open gives me some hope that the weaker question that I'm interested in has been (partially) answered in the affirmative. $\endgroup$ – Frank'a Waaldijk Jan 10 '18 at 11:56
  • $\begingroup$ I'm not sure if I understand your remark about having to specify the model of computation. I would think that there is some robustness in the idea of poly-time and poly-space, in the sense that if the above question has an answer in any common model of computation, than that answer applies to other models as well? $\endgroup$ – Frank'a Waaldijk Jan 10 '18 at 12:00
  • $\begingroup$ Could you shed some light on the relation between your question on cs.stackexchange and the above question? (this is just my ignorance, but I don't readily understand your question there enough to link it to my own). Thanks in advance! $\endgroup$ – Frank'a Waaldijk Jan 10 '18 at 12:02
  • $\begingroup$ (by the way I'm voting for your answer, but I won't accept it as the definite answer just yet, in the hope that some improvement can be found.) $\endgroup$ – Frank'a Waaldijk Jan 10 '18 at 12:15
3
$\begingroup$

I suspect that what you're hoping for—i.e., that for all $a$ and $b$ there exists $c$ such that $\mathrm{DTISP}(n^a, n^b) \subseteq \mathrm{DTISP}(n^c, n^{b/2})$—is false, but for sure nobody has proved this. In fact I suspect it may not even be true that $\mathrm{DTISP}(n^a,n^b) \subseteq\mathrm{DSPACE}(n^{b/2})$ (i.e., I suspect you cannot compensate for the loss of space with any amount of time). Certainly, if we consider all problems solvable in space $O(n^b)$ (with no restrictions on time), then the space hierarchy theorem tells us that we will be able to solve certain problems that are simply unsolvable in space $O(n^{b/2})$, no matter how much time we give ourselves. But settling your question will probably require proving a timespace hierarchy theorem, and very little is known unconditionally about such things (see this question on CS Theory Stackexchange for some information). As another illustration of our ignorance about time-space tradeoffs, note that it is not known whether a problem that can be solved in polynomial time, and that can also be solved (possibly by a different algorithm) in polylogarithmic space, is in SC (i.e., is solvable is polynomial time and polylogarithmic space simultaneously).

$\endgroup$
  • $\begingroup$ thanx Timothy for summarizing your comments in the chat and above [btw i voted for this answer as well]. still, i believe that for polytime algos some space loss can be compensated, albeit perhaps not in polytime. right now i only have a sketchy argument for this though. $\endgroup$ – Frank'a Waaldijk Jan 24 '18 at 9:22

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.