1
$\begingroup$

I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have

$$ NSPACE(S(n)) \subseteq DSPACE(S(n)^2) $$

Am wondering, what happens if $S(n)$ is fully time-constructible instead, could we have the stronger result $NSPACE(S(n)) \subseteq DSPACE(S(n))$ ? ...

For instance, for fully time-constructible $S(n))$, we have the result :

$$ NSPACE(S(n)) \subseteq \bigcup DTIME(c^{S(n)}) \text{ for } c \geq 1 $$

However, we also have:

$$ \bigcup DTIME(c^{S(n)}) \subseteq NTIME(S(n)) \subseteq DSPACE(S(n)) $$

where the first containment follows given that for a fully time constructible $S(n)$, we have that $c^{S(n)}$ can be 'simulated' by the non-determinisitc branches of an $NTIME$ machine..

Combining the two statements above, we have:

$$ NSPACE(S(n)) \subseteq DSPACE(S(n)) $$

for fully time-constructible $S(n))$... But is this result correct or am I missing something?

$\endgroup$
5
  • $\begingroup$ It is conjectured that $\mathsf{L} \neq \mathsf{NL}$, that $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$, and so on. $\endgroup$ Commented Jun 7, 2020 at 9:34
  • 1
    $\begingroup$ Why do you think that $\mathsf{DTIME}(c^{S(n)}) \subseteq \mathsf{NTIME}(S(n))$? $\endgroup$ Commented Jun 7, 2020 at 9:35
  • $\begingroup$ @YuvalFilmus, I was writing more from a hunch .... since the $c$ in the base is a constant, the non-deterministic tree can branch out by a factor of $c$ at each level, with each branch having a depth of $S(n)$ ... given that $S(n) \geq log(n)$ as $S(n)$ is time-constructible, we can make a clock for it .. $\endgroup$
    – Link L
    Commented Jun 7, 2020 at 9:43
  • 1
    $\begingroup$ Can you decide whether a given Turing machine halts in $2^n$ time using polynomial nondeterministic time? $\endgroup$ Commented Jun 7, 2020 at 9:45
  • $\begingroup$ @YuvalFilmus, oh okay, yes, it's not possible for that one ... so I guess that gives a language $<M,w>$ that is not in $NTIME(S(n))$, i.e. $M$ accepts $w$ in $DTIME(c^{S(n)})$ $\endgroup$
    – Link L
    Commented Jun 7, 2020 at 9:53

1 Answer 1

1
$\begingroup$

Space-constructibility is a red herring. The real problem in your argument is the step $$ \mathsf{DTIME}(c^{S(n)}) \subseteq \mathsf{NTIME}(S(n)), $$ which is not expected to hold in general. For example, the problem of deciding whether an input Turing machine halts in time $2^n$ can be solved in deterministic exponential time, but is conjectured not to be solvable in nondeterministic polynomial time.

Furthermore, while it's not clear whether Savitch's theorem is tight, it is expected that in general $\mathsf{DSPACE}(s(n)) \neq \mathsf{NSPACE}(s(n))$. For example, it is believed that $\mathsf{L} \neq \mathsf{NL}$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.