Can nondeterminism speed-up deterministic computation? If yes, how much?

By speeding-up deterministic computation by nondeterminism I mean results of the form:

$\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n)$

E.g. something like

$\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

What is the best known speed-up result of deterministic computation by nondeterminism? What about $\mathsf{\Sigma^P_kTime}(n)$ or even $\mathsf{ATime}(n)$ in place of $\mathsf{NTime}(n)$?

Assume that complexity classes are defined using multiple-tape Turing machines to avoid the well-know peculiarities of the sub-quadratic time single-tape Turing machines.

  • 3
    $\begingroup$ (By Theorem 4.1 and the Time Hierarchy Theorem, your example can't hold for 1-tape TMs.) ​ ​ $\endgroup$
    – user6973
    Apr 24, 2016 at 22:48

3 Answers 3


You should not expect an exciting speed-up. We have


and the best known simulation of deterministic time by space is still the Hopcroft–Paul–Valiant theorem

$$\mathrm{DTIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)/\log f(n)).$$

Thus, nondeterminism or alternation is not known to give speed-up by more than a logarithmic factor. (I suspect no super-linear speed-up is known either, though I’m not sure if the HPV theorem can’t be made to work with ATIME in place of DSPACE.)

  • 1
    $\begingroup$ For one-tape online Turing machines, it is folklore that $NTIME(n) \subseteq DSPACE(\sqrt{n})$. $\endgroup$ Apr 25, 2016 at 17:28
  • 1
    $\begingroup$ For two-tape Turing machines, we have $DTIME(n) \subseteq DSPACE(n/\log(n))$ as stated above. $\endgroup$ Apr 25, 2016 at 17:29
  • 2
    $\begingroup$ The question is about multitape Turing machines. $\endgroup$ Apr 25, 2016 at 17:34
  • 4
    $\begingroup$ I just wanted to provide additional clarification for the interested reader. $\endgroup$ Apr 25, 2016 at 17:35
  • 2
    $\begingroup$ By Paul-Pippenger-Szemerédi-Trotter, the first inclusion is $\text{DTIME}(f(n)) \subsetneq \text{NTIME}(f(n))$ for the special case where $f(n)=n$. $\endgroup$ Apr 26, 2016 at 23:44

There are two distinct concepts:

(1) Efficient simulation of deterministic machines by non-deterministic machines.

(2) Speed-up results that are obtained by applying a simulation over and over again.

I don't know of any efficient simulation of deterministic machines by non-deterministic ones, but I know of several speed-up results that could be used if efficient simulations exist.

Consider the class $NTIGU(t(n), g(n))$ of languages that are decidable by a non-deterministic Turing machine running for $t(n)$ time using only $g(n)$ non-deterministic guesses. In other words, the witness length is bounded by $g(n)$.

If you have a more efficient simulation using only $\log(n)$ non-deterministic guesses, then I believe you can speed it up quite a bit. In particular, I believe you can prove the following:

If $DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$, then $DTIME(2^{\sqrt{n}}) \subseteq NTIME(n)$.

If you find this interesting, then I can write-up the proof.

Ryan Williams introduced some related speed-ups in "Improving Exhaustive Search Implies Superpolynomial Lower Bounds".

  • 1
    $\begingroup$ As you can see, $DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$ is a rather big assumption and it is quite reasonable that you could prove the hypothesis to be false. Let me know if you do. :) $\endgroup$ Apr 25, 2016 at 18:48
  • $\begingroup$ @AndrasSalamon : ​ How does that $\subseteq$ follow from exhaustive search? ​ ​ ​ ​ $\endgroup$
    – user6973
    Apr 27, 2016 at 22:34
  • $\begingroup$ @RickyDemer you are right, it does not; have removed the comments. I was implicitly assuming that the nondeterminism was at the end of the computation, but it should be assumed to be at the beginning. $\endgroup$ Apr 28, 2016 at 8:07
  • $\begingroup$ Update: Finally started writing up the proposed speed up result that I mentioned. It appears to be a bit different than other speed up results that I found. Please feel free to reply or email me if you're interested in discussing. Thank you! :) $\endgroup$ Jul 18, 2019 at 17:57
  • 1
    $\begingroup$ would certainly take a look, this is an intriguing approach. $\endgroup$ Jul 21, 2019 at 6:04

Here is an explanation for why a general quartic nondeterministic speed-up of deterministic computation even if true would be hard to prove:

Assume that a general quartic nondeterministic speed-up of deterministic computation like $\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n)$ holds. For the sake of contradiction, assume that $\mathsf{SAT} \in \mathsf{DTime}(o(n^2/\lg n))$. There is a quadratic-time reduction from any problem in $\mathsf{NTime}(n)$ to $\mathsf{SAT}$. Combining these we would have $\mathsf{DTime}(n^4) \subseteq \mathsf{DTime}(o(n^4/\lg n))$ contradicting the time hierarchy theorem.

Therefore, a general quartic nonterministic speed-up of deterministic computation would imply a lower-bound for $\mathsf{SAT}$:

$\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n) \to \mathsf{SAT} \notin \mathsf{DTime}(o(n^2/\lg n))$.

Therefore proving a general quadratic nondeterministic speed-up of deterministic computation is at least as hard as proving almost quadratic lower-bounds on $\mathsf{SAT}$.

Similarly, for any well-behaving function $f(n)$:

$\mathsf{DTime}(f(n^2)) \subseteq \mathsf{NTime}(n) \to \mathsf{SAT} \notin \mathsf{DTime}(o(f(n)/\lg n))$.

(If in place of $\mathsf{SAT}$ we pick a problem which is hard for $\mathsf{NTime}(n)$ under linear-time reductions then this would give $f(n)/\lg n$ lower bound for that problem. If we fix the number of the machine tapes to some $k\geq 2$ then we can use Fürer's time hierarchy theorem which does not have the $\lg n$ factor.)

  • $\begingroup$ Since we don't even know that SAT is not in DTime(n), we don't know an $\omega(n \lg ⁡n)^2$ speed-up. $\endgroup$
    – Kaveh
    Apr 27, 2016 at 20:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.