# If NP is a subset of DTIME[n^O(log n)] then what happens?

If $$\mathsf{NP}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$$ then what happens? Does it imply $$\mathsf{NP}\neq \mathsf{EXP}$$? Is there any other consequences such as $$\mathsf{BPP}\neq \mathsf{EXP}$$? Does it also give $$\mathsf{PSPACE}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$$?

• "Does it imply $\textbf{NP} \neq \textbf{EXP}$?" Yes. This follows from the time hierarchy theorem. – dkaeae Mar 1 '19 at 20:44

If $$\textbf{NP} \subseteq \textbf{DTIME}(n^{O(\log n)})$$, then we get $$\textbf{P}^\textbf{NP} \subseteq \textbf{P}^{\textbf{DTIME}(n^{O(\log n)})} = \textbf{DTIME}(n^{O (\log n)})$$. Continuing this reasoning, the entire polynomial hierarchy $$\textbf{PH}$$ is contained in $$\textbf{DTIME}(n^{O(\log n)})$$. By the time hierarchy theorem, $$\textbf{DTIME}(n^{O(\log n)})$$ is a proper subset of $$\textbf{EXP}$$ (and even of $$\textbf{E} = \textbf{DTIME}(2^{O(n)})$$), so $$\textbf{PH} \neq \textbf{EXP}$$. In particular, we also get $$\textbf{NP} \neq \textbf{EXP}$$ and $$\textbf{BPP} \neq \textbf{EXP}$$ because both $$\textbf{NP}$$ and $$\textbf{BPP}$$ are in the polynomial hierarchy. For $$\textbf{BPP}$$ this is not that surprising since we already suspect it is contained in subexponential time.
What happens for $$\textbf{PSPACE}$$? Not much, as long as I'm aware of. We have $$\textbf{PH} \subseteq \textbf{PP}$$ and $$\textbf{PH} \subseteq \textbf{P}^\textbf{#P}$$ (by Toda's theorem), but I don't see any direct consequence for $$\textbf{PP}$$, let alone $$\textbf{PSPACE}$$.
• @dkaee I would have thought $PP$ would also be in quasipolynomial. – T.... Mar 2 '19 at 20:13
• Why is it so? I am not aware of any reductions from $\mathbf{PP}$ to something below it. We can approximate $\#\mathbf{P}$ using $\mathbf{BPP}$ machines with $\mathbf{NP}$ oracle, but that's another story. – dkaeae Mar 4 '19 at 10:58
• Not necessarily. To distinguish $2^n$ from $2^n - 1$ you then need zero error. You could frame it as a promise problem, but then correspondence to the original classes is no longer guaranteed. – dkaeae Mar 4 '19 at 12:54
• so $PH\subseteq \Sigma_{m}^P$ would be in $DTIME(n^{O(\log n)})$ if $m=O((\log n)^c)$ at any fixed $c>0$ correct? – T.... Mar 4 '19 at 13:04