Skip to main content
2 of 2
added 72 characters in body; edited title
xskxzr
  • 7.6k
  • 5
  • 23
  • 47

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

Turbo
  • 2.9k
  • 14
  • 27