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

  • 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.
    Jul 28, 2018 at 10:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.