Assume $NTime(2^n) \subseteq NSpace(n^k)$, for some fixed $k$. Is it possible to imply that $EXP = PSPACE$? and what about $NEXP = PSPACE$? It seems the answer might be YES, because this question seems to be equivalent to the open question $EXP=PSPACE$?
Can it be shown using some padding argument?

  • $\begingroup$ Are you aware of Savitch's theorem? $\endgroup$ – dkaeae Jun 14 '19 at 14:28
  • $\begingroup$ I can see why it leads to NEXP=PSPACE. But how Savitch theorem is related to EXP=PSPACE? $\endgroup$ – LioH Jun 16 '19 at 15:01

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.