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.

$\endgroup$
  • $\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 Dec 1 '17 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 Dec 1 '17 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 Dec 1 '17 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 Dec 1 '17 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 Dec 1 '17 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.