# Savitch's theorem for time complexity

Is it known that an analog of Savitch's theorem for time complexity is impossible, or is this an open question? More formally, is $$\exists d\ \forall c : \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(n^{cd})$$ impossible? (Here $$n$$ is the input length.)

This statement guarantees a universal polynomial simulation overhead and is thus seemingly stronger than $$\mathsf{P} = \mathsf{NP}$$ which only implies an existential polynomial overhead, i.e., for each language $$L$$ there exists some overhead $$d_L$$.

• This is equivalent to P = NP. There is a constant $k$ ($2$ or so) such that for all $c$, every language in $\mathrm{NTIME}(n^c)$ has a $\mathrm{DTIME}(n^{kc})$-reduction to SAT. Thus, if SAT is in $\mathrm{DTIME}(n^d)$, then $\mathrm{NTIME}(n^c)\subseteq\mathrm{DTIME}(n^{kcd})$ for all $c$. Commented Dec 5, 2022 at 16:36
• Thanks @EmilJeřábek. I guess the $\mathsf{DTIME}(n^{kc})$ reduction to SAT comes directly from Cook's original proof of NP-completeness of SAT? Commented Dec 5, 2022 at 16:43
• Yes, indeed.  Commented Dec 5, 2022 at 19:14
• The "trivial" simulation of a non-deterministic machine (by a deterministic machine), by trying all possible values of each transition, gives you $\text{NTIME}(t(n))\subseteq \text{DTIME}(2^{t(n)})$ (given certain restrictions on the Turing Machine model). As far as I know, this is the best known, but I'm happy to stand corrected. Commented Dec 5, 2022 at 21:58