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).

| cite | improve this answer | |
  • $\begingroup$ 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.. $\endgroup$ – Steve Peters Nov 19 '13 at 23:00

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.