3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ @dkaee I would have thought $PP$ would also be in quasipolynomial. $\endgroup$ – T.... Mar 2 at 20:13
  • $\begingroup$ 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. $\endgroup$ – dkaeae Mar 4 at 10:58
  • $\begingroup$ doesn't approximmation give msb? $\endgroup$ – T.... Mar 4 at 11:46
  • $\begingroup$ 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. $\endgroup$ – dkaeae Mar 4 at 12:54
  • $\begingroup$ 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? $\endgroup$ – T.... Mar 4 at 13:04

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.