0
$\begingroup$

Is $co-NSPACE(n^2) \subsetneq DSPACE(n^5)?$

From Savitch theorem $co-NSPACE(n^2) \subset DSPACE(n^4) \implies co-NSPACE(n^2) \subset DSPACE(n^5) $

and as $ PSPACE = NPSPACE$ we can go further to $ DSPACE(n^2)\subset DSPACE(n^5)$ (and this observation already doesn't make sense for me as it's obvious...) but I'm stuck with it and dont know which steps should I take here.

I feel like the answer to the question is "yes, it is", and I think Space hierarchy $DSpace(o(s2)) \subsetneq DSpace(s2)$ might be useful here, but I do not know how to apply it. Maybe this proof should be done by a TM simulation? Any suggestions?

$\endgroup$

0

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.