I need help with the following:
Let $k\in \mathbb{N}$, define:

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.

  • $\begingroup$ The second one "is almost immediately" resolved by a different theorem. $\;$ $\endgroup$
    – user12859
    Commented May 24, 2014 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$ Commented May 24, 2014 at 10:51

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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