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.