HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dtimewhatlogthenhappenssubset

Problem

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

Solution

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

Context

StackExchange Computer Science Q#104994, answer score: 3

Revisions (0)

No revisions yet.