Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n)) As said in the title, i am quite curious wether
NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n))
I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n))
due to linear space reduction (i.e. some sort of super character representing k characters)
But since neighter n nor n^2 is linear, we cant use this here.
Thanks for your advise!
Yes. Clearly NSPACE($2^{O(n)}$) $\subseteq $  NSPACE($n^2 \cdot 2^{O(n)}$).
To show that NSPACE($2^{O(n)}$) $\supseteq $  NSPACE($n^2 \cdot 2^{O(n)}$) it suffices to notice that $n^2  \cdot 2^{O(n)} = 2^{O(n) + 2\log n}$ and $O(n)+2\log n =O(n)$.