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

  • 6
    $\begingroup$ 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$. $\endgroup$ Commented Dec 5, 2022 at 16:36
  • $\begingroup$ 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? $\endgroup$ Commented Dec 5, 2022 at 16:43
  • $\begingroup$ Yes, indeed. $ $ $\endgroup$ Commented Dec 5, 2022 at 19:14
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Dec 5, 2022 at 21:58


Your Answer

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