<p>Note that even a result along the lines of $\mathsf{DTime}(\tilde{O}(n^2)) \subseteq \mathsf{NTime}(n^{2-\epsilon})$ would <a href="http://arxiv.org/abs/1601.04743">violate NSETH</a> as univariate polynomial identity testing (as defined in section 3.2) can be solved in $\tilde{O}(n^2)$ time deterministically, but there doesn't seem to be an obvious way to use nondeterminism to help prove identity.</p>

CC BY-SA 3.0
2016-04-28T06:47:15.333Z
2016-04-28T06:47:15.333Z
Joe Bebel
<p>Consider computing the gcd from the primitive operations of addition, subtraction, division, and remainder. The best known deterministic algorithm is the Euclidean algorithm, which takes logarithmic time in the magnitude of the smaller input (where &quot;time&quot; here means the number of calls to the primitive operations), i.e., linear in the <em>length</em> of the input. This has been <a href="https://www.cambridge.org/core/journals/bulletin-of-symbolic-logic/article/abs/is-the-euclidean-algorithm-optimal-among-its-peers/B1E4601D450EDB15BED5EE0360757D5B" rel="nofollow noreferrer">conjectured</a> to be optimal.</p>
<p>Whereas, there is a nondeterministic algorithm (Pratt's algorithm) which takes time <span class="math-container">$\log \log n$</span>, where <span class="math-container">$n$</span> is the magnitude of the smaller input. So as far as anyone knows, there's an exponential gap between the best deterministic and nondeterministic complexity.</p>
<p>So of course this is not time on a Turing machine, but it does show the possibility for more dramatic speedups with very natural notions of time.</p>

CC BY-SA 4.0
2023-05-01T15:44:54.097Z
This does not answer the question. There are, of course, many *particular* languages for which we conjecture that nondeterminism provides a (possibly even exponential) speed-up: for example, all NP-complete languages. However, that’s not the question. The question is whether it is possible that nondeterminism provides nontrivial  speed-up for *all* languages.
Emil Jeřábek
CC BY-SA 4.0
2023-04-07T16:30:40.097Z
2023-04-07T16:30:40.097Z
Siddharth
<p>This is a follow up to 
<a href="https://cstheory.stackexchange.com/q/34488/">nondeterministic speed-up of deterministic computation</a>.</p>

<p>Is it plausible that nondeterminism (or more generally alternation)
would allow a general quadratic speed-up of deterministic computation?
Or are there any known implausible consequences for something like
 $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$?</p>

CC BY-SA 3.0
2016-05-01T18:24:07.883Z
I'm not sure but I think by similar arguments that you used in your previous question we have $$\mathsf{TMSAT}=\{<a,x,1^n,1^t>:\exists u\in \{0,1\}^n\: s.t. \: M_a\: outputs\:1\: on\: input\: <x,u> \: within \: t \: steps \}$$ is not in $\mathsf{DTIME}(n^2/\lg{n})$. Actually $\mathsf{TMSAT}$ is not in $\mathsf{DTIME}(n)$, because $\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$, but I don't know any better lower bounds.
Erfan Khaniki
CC BY-SA 3.0
2016-05-01T23:43:16.153Z
@Erfan, my argument doesn't show it is not, it neither shows that it is unlikely, it just shows that _proving that it is_ is unknown and difficult for $\omega(n\lg n)^2$.
Kaveh
CC BY-SA 3.0
2016-05-02T06:52:55.537Z
Yes, you are right. Actually this argument shows that it is hard to prove $\mathsf{DTIME}(n^2)\subseteq \mathsf{NTIME}(n)$.
Erfan Khaniki
<cc.complexity-theory><nondeterminism><speed-up><alternation><tradeoff>
Is a quadratic nondeterminism speed-up of deterministic computation plausible?
Kaveh
# Is a quadratic nondeterminism speed-up of deterministic computation plausible?

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

This is a follow up to
[nondeterministic speed-up of deterministic computation](https://cstheory.stackexchange.com/q/34488/).

Is it plausible that nondeterminism (or more generally alternation)
would allow a general quadratic speed-up of deterministic computation?
Or are there any known implausible consequences for something like
$\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$?

**Tags:** cc.complexity-theory, nondeterminism, speed-up, alternation, tradeoff
> **Comments:**
> **username_1**: I'm not sure but I think by similar arguments that you used in your previous question we have $$\mathsf{TMSAT}=\{<a,x,1^n,1^t>:\exists u\in \{0,1\}^n\: s.t. \: M_a\: outputs\:1\: on\: input\: <x,u> \: within \: t \: steps \}$$ is not in $\mathsf{DTIME}(n^2/\lg{n})$. Actually $\mathsf{TMSAT}$ is not in $\mathsf{DTIME}(n)$, because $\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$, but I don't know any better lower bounds.  
> **username_0**: @Erfan, my argument doesn't show it is not, it neither shows that it is unlikely, it just shows that _proving that it is_ is unknown and difficult for $\omega(n\lg n)^2$.  
> **username_1**: Yes, you are right. Actually this argument shows that it is hard to prove $\mathsf{DTIME}(n^2)\subseteq \mathsf{NTIME}(n)$.  

---

## 2 answers

### Answer by username_2 on 2016-04-28. Score: 10

Note that even a result along the lines of $\mathsf{DTime}(\tilde{O}(n^2)) \subseteq \mathsf{NTime}(n^{2-\epsilon})$ would [violate NSETH](http://arxiv.org/abs/1601.04743) as univariate polynomial identity testing (as defined in section 3.2) can be solved in $\tilde{O}(n^2)$ time deterministically, but there doesn't seem to be an obvious way to use nondeterminism to help prove identity.


---

### Answer by username_3 on 2023-04-07. Score: 2

Consider computing the gcd from the primitive operations of addition, subtraction, division, and remainder. The best known deterministic algorithm is the Euclidean algorithm, which takes logarithmic time in the magnitude of the smaller input (where "time" here means the number of calls to the primitive operations), i.e., linear in the *length* of the input. This has been [conjectured](https://www.cambridge.org/core/journals/bulletin-of-symbolic-logic/article/abs/is-the-euclidean-algorithm-optimal-among-its-peers/B1E4601D450EDB15BED5EE0360757D5B) to be optimal.

Whereas, there is a nondeterministic algorithm (Pratt's algorithm) which takes time $\log \log n$, where $n$ is the magnitude of the smaller input. So as far as anyone knows, there's an exponential gap between the best deterministic and nondeterministic complexity.

So of course this is not time on a Turing machine, but it does show the possibility for more dramatic speedups with very natural notions of time.

> **Comments:**
> **username_4**: This does not answer the question. There are, of course, many *particular* languages for which we conjecture that nondeterminism provides a (possibly even exponential) speed-up: for example, all NP-complete languages. However, that’s not the question. The question is whether it is possible that nondeterminism provides nontrivial  speed-up for *all* languages.  

---

