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.

$\endgroup$
  • 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 May 21 '15 at 13:00
  • $\begingroup$ @Shaull No, I haven't seen that theorem. $\endgroup$ – user23522 May 21 '15 at 13:05
  • $\begingroup$ It's an old result and appears in several textbooks. You can start here for references and proofs. $\endgroup$ – Shaull May 21 '15 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 May 21 '15 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 May 21 '15 at 14:55
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)]$.

$\endgroup$

Your Answer

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