Skip to main content
Computer Science

Return to Question

added 72 characters in body; edited title
Source Link
xskxzr
xskxzr
  • 7.6k
  • 5
  • 23
  • 47

If $NP\subseteq DTIME[n^{ONP is a subset of DTIME[n^O(\loglog n)}]$] then what happens?

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

If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens?

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

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

Tweeted twitter.com/StackCompSci/status/1102358227432411136
Source Link
Turbo
Turbo
  • 2.9k
  • 14
  • 27

If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens?

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