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$
  • $\begingroup$ It is conjectured that $\mathsf{L} \neq \mathsf{NL}$, that $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$, and so on. $\endgroup$ – Yuval Filmus Jun 7 at 9:34
  • 1
    $\begingroup$ Why do you think that $\mathsf{DTIME}(c^{S(n)}) \subseteq \mathsf{NTIME}(S(n))$? $\endgroup$ – Yuval Filmus Jun 7 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 Jun 7 at 9:43
  • 1
    $\begingroup$ Can you decide whether a given Turing machine halts in $2^n$ time using polynomial nondeterministic time? $\endgroup$ – Yuval Filmus Jun 7 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 Jun 7 at 9:53
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}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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