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

  • $\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 '16 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 '16 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 '16 at 6:52

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.


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.