# Space complexity problem, relation between $DSPACE(log^kn)$ and $DSPACE(log^{k+1}n)$

I need help with the following:
Let $k\in \mathbb{N}$, define:
$L^k=DSPACE(O(log^k(n)))$
$NL^k=NSPACE(O(log^k(n)))$
and:
$PolyL=\bigcup_{k=1}^{\infty}L^k$
$PolyNL=\bigcup_{k=1}^{\infty}NL^k$

I need to prove, disprove or to determine if it is an open question:
1. For every $k\in \mathbb{N}$ it holds that $NL^k\subseteq L^{2k}$
2. There exist $k\in \mathbb{N}$ s.t. $L^k=L^{k+1}$

The first one is easy, since it is almost immediately the result of Savitch's theorem.
The second one I'm not sure... I'd love to get some lead there.

• The second one "is almost immediately" resolved by a different theorem. $\;$
– user12859
May 24 '14 at 9:31
• The only two theorems we've learned so far are Savitch and Immerman ($NL=CoNL$), and I don't see how Immerman has anything to do here... May 24 '14 at 10:51