3
$\begingroup$

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

$\endgroup$
  • 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 '18 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.