<p>Is it known that an analog of Savitch's theorem for time complexity is impossible, or is this an open question?
More formally, is <span class="math-container">$\exists d\ \forall c : \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(n^{cd})$</span> impossible? (Here <span class="math-container">$n$</span> is the input length.)</p>
<p>This statement guarantees a <em>universal</em> polynomial simulation overhead and is thus seemingly stronger than <span class="math-container">$\mathsf{P} = \mathsf{NP}$</span> which only implies an <em>existential</em> polynomial overhead, i.e., for each language <span class="math-container">$L$</span> there exists some overhead <span class="math-container">$d_L$</span>.</p>

CC BY-SA 4.0
2022-12-05T16:36:26.807Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2022-12-05T16:43:03.143Z
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?
Nicholas Brandt
CC BY-SA 4.0
2022-12-05T19:14:10.670Z
Yes, indeed. $ $
Emil Jeřábek
CC BY-SA 4.0
2022-12-05T21:58:13.263Z
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.
Lieuwe Vinkhuijzen
<cc.complexity-theory><time-complexity><nondeterminism>
Savitch's theorem for time complexity
Nicholas Brandt
# Savitch's theorem for time complexity

(Asked by: username_0 on 2022-12-05)

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

**Tags:** cc.complexity-theory, time-complexity, nondeterminism
> **Comments:**
> **username_1**: 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$.  
> **username_0**: 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?  
> **username_1**: Yes, indeed. $ $  
> **username_2**: 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.  

---

## 0 answers

