# Is a quadratic nondeterminism speed-up of deterministic computation plausible?

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

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