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

<p>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.</p>

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

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

<p>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}$.</p>

<p>Similarly, for any well-behaving function $f(n)$:</p>

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

<p>(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 <a href="https://cstheory.stackexchange.com/a/16286/">Fürer's time hierarchy theorem</a> 
which does not have the $\lg n$ factor.)</p>

CC BY-SA 3.0
2016-04-27T20:52:33.690Z
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.
Kaveh
CC BY-SA 3.0
2016-04-27T17:22:03.853Z
2016-04-27T17:53:39.250Z
2017-04-13T12:32:28.167Z
Kaveh
<p>There are two distinct concepts:</p>

<p><strong>(1)</strong> Efficient simulation of deterministic machines by non-deterministic machines.</p>

<p><strong>(2)</strong> Speed-up results that are obtained by applying a simulation over and over again.</p>

<p>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.</p>

<blockquote>
  <p>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)$.</p>
  
  <p>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:</p>
  
  <p>If $DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$, then
  $DTIME(2^{\sqrt{n}}) \subseteq NTIME(n)$.</p>
</blockquote>

<p>If you find this interesting, then I can write-up the proof.</p>

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

CC BY-SA 3.0
2016-04-25T18:48:06.650Z
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.  :)
Michael Wehar
CC BY-SA 3.0
2016-04-28T08:07:14.603Z
@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.
András Salamon
CC BY-SA 4.0
2019-07-18T17:57:13.340Z
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!  :)
Michael Wehar
CC BY-SA 4.0
2019-07-21T06:04:21.143Z
would certainly take a look, this is an intriguing approach.
András Salamon
CC BY-SA 4.0
2019-07-21T08:07:22.913Z
@AndrásSalamon Awesome!  It's a work in progress, but I will share the BitBucket repository with you.  :)
Michael Wehar
CC BY-SA 4.0
2019-07-21T08:11:04.370Z
@AndrásSalamon I just shared it with the email address I have of yours and gave you write access.  If you didn't get it, please let me know.  If you like it and think you can contribute, then you're welcome to be a co-author.
Michael Wehar
CC BY-SA 4.0
2023-04-08T15:08:24.667Z
Andras and I recently published a paper related to this!  :)
Michael Wehar
CC BY-SA 3.0
2016-04-25T17:14:48.180Z
2016-04-25T17:48:06.497Z
2016-04-25T17:48:06.497Z
Michael Wehar
<p>You should not expect an exciting speed-up. We have</p>

<p>$$\mathrm{DTIME}(f(n))\subseteq\mathrm{NTIME}(f(n))\subseteq\mathrm{ATIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)),$$</p>

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

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

<p>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.)</p>

CC BY-SA 3.0
2016-04-25T17:28:25.433Z
For one-tape online Turing machines, it is folklore that $NTIME(n) \subseteq DSPACE(\sqrt{n})$.
Michael Wehar
CC BY-SA 3.0
2016-04-25T17:29:38.767Z
For two-tape Turing machines, we have $DTIME(n) \subseteq DSPACE(n/\log(n))$ as stated above.
Michael Wehar
CC BY-SA 3.0
2016-04-25T17:34:42.263Z
The question is about multitape Turing machines.
Emil Jeřábek
CC BY-SA 3.0
2016-04-25T17:35:31.277Z
I just wanted to provide additional clarification for the interested reader.
Michael Wehar
CC BY-SA 3.0
2016-04-26T23:44:48.120Z
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$.
András Salamon
CC BY-SA 3.0
2016-04-28T17:36:46.237Z
The one-tape online Turing machine result can be found in "Relations Between Time and Tape Complexities".
Michael Wehar
CC BY-SA 3.0
2016-04-25T17:04:00.627Z
2016-04-25T17:04:00.627Z
Emil Jeřábek
<p>Can nondeterminism speed-up deterministic computation? If yes, how much?</p>

<p>By speeding-up deterministic computation by nondeterminism I mean results of the form:</p>

<blockquote>
  <p>$\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n)$</p>
</blockquote>

<p>E.g. something like</p>

<blockquote>
  <p>$\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$</p>
</blockquote>

<p>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)$?</p>

<p>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.</p>

<cc.complexity-theory><nondeterminism><speed-up><alternation><tradeoff>
Nondeterministic speed-up of deterministic computation
Kaveh
# Nondeterministic speed-up of deterministic computation

(Asked by: username_0 on 2016-04-24)

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.

**Tags:** cc.complexity-theory, nondeterminism, speed-up, alternation, tradeoff


---

## 3 answers

### Answer by username_3 on 2016-04-25. Score: 11 | Accepted answer

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

$$\mathrm{DTIME}(f(n))\subseteq\mathrm{NTIME}(f(n))\subseteq\mathrm{ATIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)),$$

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

> **Comments:**
> **username_1**: For one-tape online Turing machines, it is folklore that $NTIME(n) \subseteq DSPACE(\sqrt{n})$.  
> **username_1**: For two-tape Turing machines, we have $DTIME(n) \subseteq DSPACE(n/\log(n))$ as stated above.  
> **username_3**: The question is about multitape Turing machines.  
> **username_1**: I just wanted to provide additional clarification for the interested reader.  
> **username_2**: 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$.  
> **username_1**: The one-tape online Turing machine result can be found in "Relations Between Time and Tape Complexities".  

---

### Answer by username_0 on 2016-04-27. Score: 6

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](https://cstheory.stackexchange.com/a/16286/)
which does not have the $\lg n$ factor.)

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_1 on 2016-04-25. Score: 6

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

> **Comments:**
> **username_1**: 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.  :)  
> **username_2**: @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.  
> **username_1**: 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!  :)  
> **username_2**: would certainly take a look, this is an intriguing approach.  
> **username_1**: @AndrásSalamon Awesome!  It's a work in progress, but I will share the BitBucket repository with you.  :)  
> **username_1**: @AndrásSalamon I just shared it with the email address I have of yours and gave you write access.  If you didn't get it, please let me know.  If you like it and think you can contribute, then you're welcome to be a co-author.  
> **username_1**: Andras and I recently published a paper related to this!  :)  

---

