0
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

$\let\c\mathrm$The assumption $$\c{NTIME}(2^n)\subseteq\c{NSPACE}(n^k)\tag1$$ indeed implies $$\c{PSPACE=EXP=NEXP}$$ by a simple padding argument. The inclusions $$\c{PSPACE\subseteq EXP\subseteq NEXP}$$ hold unconditionally. In order to show $\c{NEXP\subseteq PSPACE}$, take an arbitrary language $L\in\c{NEXP}$, and let $c$ be such that $L\in\c{NTIME}(2^{n^c})$. Then the language $$L'=\{(w,1^n):w\in L,n\ge|w|^c\}$$ is in $\c{NTIME}(2^n)$, hence $$L'\in\c{NSPACE}(n^k)\subseteq\c{DSPACE}(n^{2k})\subseteq\c{PSPACE}$$ by (1) and Savitch’s theorem. Since $L$ is polynomial-time reducible to $L'$ by means of the function $w\mapsto(w,1^{|w|^c})$, it follows that $L\in\c{PSPACE}$, too.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.