<p>If a function is computable in time $T(n)$, is it computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously?</p>

<p>We won't be able to prove it, because it implies the open problems $\text{P} \neq \text{PSPACE}$ and $\text{EXPTIME} \neq \text{EXPSPACE}$.</p>

<p>I think we won't be able to disprove it either. A counterexample in the polynomial-time regime would imply the open problem $\text{P} \neq \text{L}$.  In the exponential-time regime, $\text{EXPTIME} \neq \text{PSPACE}$. But maybe there is a counterexample somewhere else.</p>

<p>My question is simply: is this statement or a similar one equivalent to any well-known conjecture?  Any references would also be appreciated.</p>

CC BY-SA 3.0
2017-12-01T21:14:55.013Z
This depends on the model but I'm pretty sure that for Turing machines the only sublinear-time computable functions are constant space and eventually periodic.  So I think we can paper over any counterexamples on the low side of polynomial.
Dan Brumleve
CC BY-SA 3.0
2017-12-01T21:18:30.913Z
I was confused why a counterexample in P would show P is not equal to L. It's immediate that a counterexample in P shows P is not equal to SC, but then I guess SC contains RL, which contains L. Is there an easier way to see this? I feel like I am missing something obvious.
Sasho Nikolov
CC BY-SA 3.0
2017-12-01T21:21:04.957Z
Suppose there is a polynomial-time computable function that is not simultaneously computable in polynomial time and $n^{o(1)}$ space.  Then it's also not simultaneously computable in polynomial time and logarithmic space so it witnesses $\text{P} \neq \text{L}$.  Remember every logarithmic-space algorithm runs in polynomial time, but that's not true for all subpolynomial space algorithms,  and this isn't enough to imply $\text{P} \neq \text{L}^2$.
Dan Brumleve
CC BY-SA 3.0
2017-12-01T21:27:55.447Z
Ah I see what I am missing. After a polynomial number of steps, the logspace algorithm will either have terminated or it will repeat its state and run forever. So you can always "clock out" after poly many steps. Thanks!
Sasho Nikolov
CC BY-SA 3.0
2017-12-02T00:19:54.173Z
Using the same argument, doesn't a counterexample with any linear/superlinear $T$ also imply $P \neq L$, since $P = L$ implies $DSPACE(f(n)) = DTIME(2^{f(n)})$ for all time-constructable $f(n) = \Omega(\log n)$? I don't think the time constructability of $T$ should not be a factor here, since (I think) $\lfloor \log T \rfloor$ is time constructable iff $T$ is.
Yonatan N
CC BY-SA 3.0
2017-12-05T18:00:02.173Z
I love these time vs space problems!  :)
Michael Wehar
CC BY-SA 3.0
2017-12-05T18:08:08.447Z
To the best of my knowledge: it's known that for appropriate functions $t(n)$, $DTIME(t(n))$ is a subset of $DSPACE(\frac{t(n)}{log(t(n))})$ for multitape Turing machines from "On Time Versus Space" by John Hopcroft, Wolfgang Paul, and Leslie Valiant.  However, it's not even known if $DTIME(t(n))$ is a subset of $DTISP(poly(t(n)), \frac{t(n)}{log(t(n))})$.
Michael Wehar
<reference-request><time-complexity><space-complexity>
The problem of whether or not every function computable in time $T(n)$ is computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously
Dan Brumleve
# The problem of whether or not every function computable in time $T(n)$ is computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously

(Asked by: username_0 on 2017-12-01)

If a function is computable in time $T(n)$, is it computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously?

We won't be able to prove it, because it implies the open problems $\text{P} \neq \text{PSPACE}$ and $\text{EXPTIME} \neq \text{EXPSPACE}$.

I think we won't be able to disprove it either. A counterexample in the polynomial-time regime would imply the open problem $\text{P} \neq \text{L}$. In the exponential-time regime, $\text{EXPTIME} \neq \text{PSPACE}$. But maybe there is a counterexample somewhere else.

My question is simply: is this statement or a similar one equivalent to any well-known conjecture? Any references would also be appreciated.

**Tags:** reference-request, time-complexity, space-complexity
> **Comments:**
> **username_0**: This depends on the model but I'm pretty sure that for Turing machines the only sublinear-time computable functions are constant space and eventually periodic.  So I think we can paper over any counterexamples on the low side of polynomial.  
> **username_1**: I was confused why a counterexample in P would show P is not equal to L. It's immediate that a counterexample in P shows P is not equal to SC, but then I guess SC contains RL, which contains L. Is there an easier way to see this? I feel like I am missing something obvious.  
> **username_0**: Suppose there is a polynomial-time computable function that is not simultaneously computable in polynomial time and $n^{o(1)}$ space.  Then it's also not simultaneously computable in polynomial time and logarithmic space so it witnesses $\text{P} \neq \text{L}$.  Remember every logarithmic-space algorithm runs in polynomial time, but that's not true for all subpolynomial space algorithms,  and this isn't enough to imply $\text{P} \neq \text{L}^2$.  
> **username_1**: Ah I see what I am missing. After a polynomial number of steps, the logspace algorithm will either have terminated or it will repeat its state and run forever. So you can always "clock out" after poly many steps. Thanks!  
> **username_2**: Using the same argument, doesn't a counterexample with any linear/superlinear $T$ also imply $P \neq L$, since $P = L$ implies $DSPACE(f(n)) = DTIME(2^{f(n)})$ for all time-constructable $f(n) = \Omega(\log n)$? I don't think the time constructability of $T$ should not be a factor here, since (I think) $\lfloor \log T \rfloor$ is time constructable iff $T$ is.  
> **username_3**: I love these time vs space problems!  :)  
> **username_3**: To the best of my knowledge: it's known that for appropriate functions $t(n)$, $DTIME(t(n))$ is a subset of $DSPACE(\frac{t(n)}{log(t(n))})$ for multitape Turing machines from "On Time Versus Space" by John Hopcroft, Wolfgang Paul, and Leslie Valiant.  However, it's not even known if $DTIME(t(n))$ is a subset of $DTISP(poly(t(n)), \frac{t(n)}{log(t(n))})$.  

---

## 0 answers

