14
$\begingroup$

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.

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

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

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

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

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

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

Improve this answer
$\endgroup$
  • $\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 '16 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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