9
$\begingroup$

This is a follow up to nondeterministic speed-up of deterministic computation.

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ May 1, 2016 at 18:24
  • $\begingroup$ @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$. $\endgroup$
    – Kaveh
    May 1, 2016 at 23:43
  • $\begingroup$ Yes, you are right. Actually this argument shows that it is hard to prove $\mathsf{DTIME}(n^2)\subseteq \mathsf{NTIME}(n)$. $\endgroup$ May 2, 2016 at 6:52

2 Answers 2

10
$\begingroup$

Note that even a result along the lines of $\mathsf{DTime}(\tilde{O}(n^2)) \subseteq \mathsf{NTime}(n^{2-\epsilon})$ would violate NSETH 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.

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 1, 2023 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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