# Nondeterministic speed-up of deterministic computation

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.

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

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

• For one-tape online Turing machines, it is folklore that $NTIME(n) \subseteq DSPACE(\sqrt{n})$. – Michael Wehar Apr 25 '16 at 17:28
• For two-tape Turing machines, we have $DTIME(n) \subseteq DSPACE(n/\log(n))$ as stated above. – Michael Wehar Apr 25 '16 at 17:29
• The question is about multitape Turing machines. – Emil Jeřábek Apr 25 '16 at 17:34
• I just wanted to provide additional clarification for the interested reader. – Michael Wehar Apr 25 '16 at 17:35
• 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 Apr 26 '16 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".

• 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 Apr 25 '16 at 18:48
• @AndrasSalamon : ​ How does that $\subseteq$ follow from exhaustive search? ​ ​ ​ ​ – user6973 Apr 27 '16 at 22:34
• @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 Apr 28 '16 at 8:07
• 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 Jul 18 '19 at 17:57
• would certainly take a look, this is an intriguing approach. – András Salamon Jul 21 '19 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.)

• 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 Apr 27 '16 at 20:52