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)}]$?
If NP is a subset of DTIME[n^O(log n)] then what happens?
Turbo
- 2.9k
- 14
- 27