6
$\begingroup$

I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires $\Omega(\text{log }n)$ space.

I believe this can be done using a crossing sequence argument. I have been trying to imitate the $DSPACE(O(1)) = REG$ proof from wikipedia.

What I have tried is:

Suppose $L \in DSPACE(S(n))$, for some $S(n) = o(\text{log } n)$ and let $M$ be an $S(n)$ space bounded TM recognizing $L$. Since $L$ is not regular, $L \notin DSPACE(O(1))$. Therefore, given $k \in \mathbb{N}$, let $x \in L$ be a string of minimal length that requires more than $k$ worktape cells.

Let $C$ be the set of configurations of $M$ on $x$. That is, $C$ is the set of tuples of the form

(state, work tape head position, work tape contents).

Then $|C| \leq |Q_M| \times S(n) \times 2^{S(n)} \leq 2^{cS(n)} = o(n)$, where $c$ is some suitable constant.

The crossing sequence at $i^{\text{th}}$ cell boundary is the sequence of such configurations occurring as the input head moves across that boundary. Each term of a crossing sequence can be any of the $|C|$ elements from $C$.

Also, length of any crossing sequence cannot be more than $|C|$; for otherwise, some configuration will repeat and $M$ will enter into an infinte loop.

Therefore, number of crossing sequences of $M$ on $x$ $\leq |C|^{|C|} \leq 2^{cS(n)2^{cS(n)}} $.

The problem is that this doesn't give the required bound. So, a cleverer argumet is needed.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Are you familiar with the theorem that $TIME[o(n\log n)]=REG$? This seems to require the exact same argument. $\endgroup$
    – Shaull
    Commented May 21, 2015 at 13:00
  • $\begingroup$ @Shaull No, I haven't seen that theorem. $\endgroup$
    – user23522
    Commented May 21, 2015 at 13:05
  • $\begingroup$ It's an old result and appears in several textbooks. You can start here for references and proofs. $\endgroup$
    – Shaull
    Commented May 21, 2015 at 13:19
  • $\begingroup$ @Shaull Thanks for the reference. I've gone through the proof of the result you suggested. I'm not sure if it can be adapted to prove the space lower bound; for time lower bounds, the crossing sequences considered are simply sequences of states whereas for space complexity results, the worktape contents have to be considered too. $\endgroup$
    – user23522
    Commented May 21, 2015 at 14:46
  • 3
    $\begingroup$ If, by contradiction, you could solve $0^n1^n$ in $o(\log n)$ space, then you could also solve it in $o(n)$ time, as you show by counting configurations. But the theorem implies that $0^n1^n$ is then regular, which it isn't. $\endgroup$
    – Shaull
    Commented May 21, 2015 at 14:55

1 Answer 1

Reset to default
2
$\begingroup$

As you correctly point out by counting configurations, it holds that $SPACE[o(\log n)]\subseteq TIME[o(n)]$.

There is a theorem stating that $TIME[o(n\log n)]=REG$. See e.g. here.

If, by contradiction, we had $\{0^n1^n: n\in \mathbb{N}\}\in SPACE[o(\log n)]$, it would then follow that $\{0^n1^n: n\in \mathbb{N}\}\in REG$, which is clearly false.

Thus, $\{0^n1^n: n\in \mathbb{N}\}$ cannot be solved in $SPACE[o(\log n)]$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The first sentence is somewhat misleading. There is a language, which is decidable in $O(\log \log n)$ in space, but is not regular. In fact, $SPACE(o(\log\log n) = SPACE(O(1))$ and the bound is tight. $\endgroup$
    – sas
    Commented Feb 6, 2023 at 14:36
  • $\begingroup$ @sas - what language? Note that SPACE(O(1))=REG. This is trivial since you can model an O(1) space TM as a two-way DFA (NFA), which are equivalent to DFAs (this is shown with crossing-sequences). $\endgroup$
    – Shaull
    Commented Feb 6, 2023 at 19:13
  • $\begingroup$ Indeed. SPACE(O(1)) = SPACE(o(loglog n)) = REG. But SPACE(O(loglog n)) is bigger than that. Theorem 4.3 and its neighbours in Oded Goldreich's lecture notes wisdom.weizmann.ac.il/~/oded/PS/CC/all.pdf provide aforementioned separation. $\endgroup$
    – sas
    Commented Feb 13, 2023 at 11:17
  • $\begingroup$ @sas - Oh, of course! Counting configurations only gives $o(n^2)$. My argument is not "somewhat misleading", it's plain wrong! Turns out I can't delete an accepted answer. $\endgroup$
    – Shaull
    Commented Feb 13, 2023 at 19:03

Your Answer

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