Skip to main content
added 847 characters in body
Source Link
Dan Brumleve
  • 2.3k
  • 17
  • 28

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.

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!

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.

Source Link
Dan Brumleve
  • 2.3k
  • 17
  • 28

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!