What is consequences of $PH\subseteq NSPACE((\log n)^2)$?
We don't even know PH is equals to L or not. I am wondering what will be happened when $PH\subseteq NSPACE((\log n)^2)$?
$\begingroup$
$\endgroup$
1
asked Jul 23, 2018 at 17:37
-
1$\begingroup$ For $NP \subseteq NSPACE((\log(n)^2)$, it contredicts the ETH, since it implies that all $NP$ problem can be solve in $n^{\log(n)}$ times. From cstheory.stackexchange.com/questions/36750/… you get that Exp-time hiearchy collapse at the second level. $\endgroup$– C.P.Commented Jul 28, 2018 at 10:31
Add a comment
|