Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

Question

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?

Answer 1

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}$.