# Extension of Time Hierarchy Theorem to LBAs

I am trying to prove:

Let there be a constructible function $t: ~\mathcal{N} \to \mathcal{N}$. Then there exists a language $L$ where $L$ is decidable by an LBA in $O(t(n))$ time, but not $o\left(\frac{t(n)}{\log t(n)}\right)$ time. You may assume that LBAs have a fixed tape alphabet and have unique symbols marking the start and end of the input.

I've read through Sipser's version of the proof (Theorem 9.10) several times, but am not sure how to apply it to LBAs. Hints only please.

It may help you to remember that LBA's are simply non-deterministic TM's with a limited tape (instead of infinite).

• Hmm so is it trivially true? That's actually what I was originally thinking, but it seemed too easy for a problem to get assigned.. – Steve Peters Nov 19 '13 at 23:00