4
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ I suspect someone here could prove that ​ length : {0,1}* $\to$ {0,1,2,3,...} $\hspace{2.14 in}$ gives a counterexample for ​ T(n) $\in \Theta(\hspace{.02 in}\log(n))$ , ​ although I've tried a little $\hspace{1.98 in}$ and not managed to show that. ​ ​ ​ ​ $\endgroup$
    – user6973
    Commented Dec 1, 2017 at 20:04
  • $\begingroup$ 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. $\endgroup$
    – Dan Brumleve
    Commented Dec 1, 2017 at 21:14
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Dec 1, 2017 at 21:18
  • $\begingroup$ 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$. $\endgroup$
    – Dan Brumleve
    Commented Dec 1, 2017 at 21:21
  • 1
    $\begingroup$ 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! $\endgroup$
    – Sasho Nikolov
    Commented Dec 1, 2017 at 21:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.