# $NTime(2^n) \subseteq NSpace(n^k)$ implies $EXP = PSPACE$?

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?

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

$$\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.