# Prove NLOGSPACE$\subset$PSPACE

Condidering the proof, NLOGSPACE$$\subset$$PSPACE

I wrote following proof:

NLOGSPACE = NSPACE$$(\log n)$$ $$\hspace{15pt} \because$$ Definition of NLOGSPACE

NSPACE$$(\log n)$$ $$\subseteq$$ DSPACE$$(\log^2 n)$$ $$\hspace{15pt} \because$$ Theorem(1)

We let $$m = \log n$$, then,

DSPACE$$(m^2)$$ $$\subset$$PSPACE $$\hspace{15pt} \because$$ Definition(2)

Therefore, NLOGSPACE$$\subset$$PSPACE.

Theorem(1): If $$S$$ is a space constructible function and $$S(n) \ge \log n$$, then NSPACE$$(S(n)) \subseteq$$ DSPACE$$(S^2(n))$$.

definition(2): PSPACE = DSPACE$$(n)\cup$$DSPACE$$(n^2)\cup$$DSPACE$$(n^3)\cup$$...$$\cup$$DSPACE$$(n^k)\cup$$...

But I am still not that sure if that "We let $$m = \log n$$" is ok, is this proving NLOGSPACE$$\subset$$PSPACE?

What would you think about a proof that says the following?

• $$NP \subset DTIME(2^n)$$
• let $$m = \log n$$, then $$DTIME(2^n) = DTIME(m) \subset P$$
• Therefore $$P = NP$$

Here, you have indeed $$DPSACE(log^2n)\subset PSPACE$$ but the argument is weird.

Also please note that Savitch's theorem already proves that $$NPSPACE \subset PSPACE$$, and you have the result you want, since $$NLOGSPACE \subset NPSPACE$$.

• Thanks for answering! How Savitch's theorem proves NPSPACE⊂PSPACE? also, where is NLOGSPACE⊂NPSPACE? Commented Apr 24, 2021 at 9:31
• The first question is true because if $f$ is a polynomial function, then $f^2$ is a polynomial function too. And $NPSPACE = \underset{f\text{ polynomial}}{NSPACE}(f(n)) \subset \underset{f\text{ polynomial}}{DSPAC}E(f(n)^2) = PSPACE$. Commented Apr 24, 2021 at 9:40
• The second question is true because $\log n = O(n)$, and so $NLOGSPACE = NSPACE(\log n) \subset DSPACE((\log n)^2) \subset DSPACE(n^2) \subset PSPACE$ Commented Apr 24, 2021 at 9:43
• I see. At $DSPACE(f(n)^2) = PSPACE$, why can you write "=", not "$\subset$"? Commented Apr 24, 2021 at 10:06
• Because the union is done on all polynomial functions. Commented Apr 24, 2021 at 10:13