0
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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$
    – Emil Jeřábek
    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$
    – Nicholas Brandt
    Dec 5, 2022 at 16:43
  • $\begingroup$ Yes, indeed. $ $ $\endgroup$
    – Emil Jeřábek
    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$
    – Lieuwe Vinkhuijzen
    Dec 5, 2022 at 21:58

0

Reset to default

Your Answer

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