1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ The second one "is almost immediately" resolved by a different theorem. $\;$ $\endgroup$ – user12859 May 24 '14 at 9:31
  • $\begingroup$ 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... $\endgroup$ – so.very.tired May 24 '14 at 10:51
2
$\begingroup$

Use the space hierarchy theorem, which is a finite form of the undecidability of the halting problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.