Nondeterministic speed-up of deterministic computation

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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