1
$\begingroup$

I have been given an assignment that I'm having a very hard time understanding.

The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (so if the language is regular, the complexity is $O(\log \log n)$). The computational model to be used is a Turing machine with one input and one work tape.

Here's an excerpt from a book called Theory of computation by Dexter C. Kozen that I will be using to prove the assumption (if it's not allowed to post such an excerpt here please let me know, I'll remove it and share just some parts there instead, I posted it whole as I consider all information there to be important).

Complexity theorem

I have read this excerpt several times and there are several parts that I wasn't able to grasp. If I understand this correctly, $N$ is equal to all possible configurations (a crossing sequence) for a single cell. On the other hand, $\sum^{m}_{i=0} N^{i}$ is equal to crossing sequences on $m$ cells. So the thing I don't understand about this is why the $n/2$ first (or last) crossing sequences have to be distinct. I suppose I understand that you'd be able to cut a part of the input string if there were two identical crossing sequences on two positions, but I don't see why the number of required distinct crossing sequences equals $n/2$ and not some other number. For example, why do we partition $x$ into 2 parts and not 4 or some other number?

One other thing that I really don't understand is the very last equation, which says "Combining (1.3), (1.4) and (1.5) and taking logs, we get $S(n) \geq \Omega (\log \log n)$." I just don't understand how it's possible to come up with this equation by taking those three mentioned equations. The first step should be replacing $N$ in those equations, which gives me these two equations:

$\frac{n}{2} \leq \sum^{m}_{i=0} (q \cdot S(n)\cdot d^{S(n)})^{i} = \frac{(q \cdot S(n)\cdot d^{S(n)})^{m+1}-1}{(q \cdot S(n)\cdot d^{S(n)})-1}$

$m \leq 2 \cdot (q \cdot S(n)\cdot d^{S(n)})$

I don't know how to combine these two equations and reach the desired equation that is $S(n) \geq \Omega (\log \log n)$. Thank you for any help in advance.

$\endgroup$
1
  • $\begingroup$ If a language is regular, its space complexity is 0. $\endgroup$ Nov 6, 2021 at 8:13

1 Answer 1

0
$\begingroup$

If I understand this correctly, $N$ is equal to all possible configurations (a crossing sequence) for a single cell.

That's not accurate: a crossing sequence is a sequence of configurations. We form the crossing sequence at position $i$ as follows: we trace the execution of the Turing machine, and whenever the head on the input tape crosses the $i$'th position (either toward position $i+1$ or toward position $i-1$), we concatenate the current configuration (state, contents of work tape, and head location on work tape) to the crossing sequence.

On the other hand, $\sum_{i=0}^m N^i$ is equal to crossing sequences on $m$ cells.

No. That's the number of crossing sequences of length at most $m$ at a single cell.

I don't understand about this is why the $n/2$ first (or last) crossing sequences have to be distinct. I suppose I understand that you'd be able to cut a part of the input string if there were two identical crossing sequences on two positions, but I don't see why the number of required distinct crossing sequences equals $n/2$ and not some other number. For example, why do we partition $x$ into 2 parts and not 4 or some other number?

Suppose that the crossing sequence $c$ occurs at position $i$. Then the crossing sequences at positions $1,\ldots,i$ are all distinct: if the crossing sequences at positions $j<k\leq i$ were identical, deleting the part of the input corresponding to positions $j+1,\ldots,k$ will result in a shorter input $x$ with the same crossing sequence $c$ (at position $i-(k-j)$. Similarly, the crossing sequences at positions $i,\ldots,n$ are all distinct. What we cannot say is that the crossing sequences at positions $1,\ldots,n$ are all distinct — the same argument doesn't work.

For the rest of the argument, we want to find as many distinct crossing sequences as possible. Therefore we take the maximum between $i$ (the number of crossing sequences corresponding to positions $1,ldots,i$) and $n-i+1$ (the number of crossing sequences corresponding to positions $i,\ldots,n$), which is always at least $n/2$.

One other thing that I really don't understand is the very last equation, which says "Combining (1.3), (1.4) and (1.5) and taking logs, we get $S(n) \ge \Omega(\log\log n)$."

The equations in question state \begin{align} N &= qS(n)d^{S(n)} \\ \frac{n}{2} &\le \frac{N^{m+1}-1}{N-1} \\ m &\le 2N \end{align} The second equation simplifies to $$ n \leq 2N^{2m}. $$ Applying the third equation, $$ n \leq 2N^{4N}. $$ Taking logarithm, $$ \log n \leq 4N\log N + \log 2. $$ If $x \leq y\log y$ then $y = \Omega(x/\log x)$, and so $$ N = \Omega\left(\frac{\log n}{\log\log n}\right). $$ Substituting the value of $N$, $$ qS(n)d^{S(n)} = \Omega\left(\frac{\log n}{\log\log n}\right). $$ Taking another logarithm, $$ \log q + \log S(n) + S(n) \log d \geq \log \log n - O(1). $$ Since $\log q + \log S(n) = o(S(n))$, the left-hand side is $O(S(n))$, and so $$ S(n) = \Omega(\log\log n). $$

$\endgroup$
5
  • $\begingroup$ Thank you very much for your explanation. I have marked it as accepted because even though this is a very complex subject for me, after studying it I can say I understand almost everything in your answer. There's just one thing I have to ask, I don't have experience in using logarithms with Big O and Big-Omega notations, why does $=\Omega\frac{log \: n}{log \: log \: n}$ equal to $\geq log \: log \: n - O(1)$ and why does $log \: q + log \: S(n)$ equal to $o(S(n))$ (alternatively $o(S(n) + S(n)log \: d = O(S(n))$? I tried to look up such logarithmic rules but I wasn't able to find anything. $\endgroup$
    – khand
    Nov 6, 2021 at 10:02
  • $\begingroup$ If $f(n) = \Omega(g(n))$, then by definition, $f(n) \geq cg(n)$ for large $n$. Taking logarithm, $\log f(n) \geq \log g(n) + \log c = \log g(n) - O(1)$ (since $\log c$ could be negative). $\endgroup$ Nov 6, 2021 at 10:55
  • $\begingroup$ You can show from first principles that $\log n + C = o(n)$. Here we think of $S(n)$ as unbounded, and so we can substitute $S(n)$ for $n$; if we wanted to be more formal, we would have to be a bit more careful, but the final result would be the same. $\endgroup$ Nov 6, 2021 at 10:57
  • $\begingroup$ So $o(n) \: + \: n \: log \:d = O(n)$ because $o(n) \: + \: n \: log \:d$ were the three parts of the initial $qnd^{n}$ equation, and $O(S(n)) \geq log \: log \: n - O(1)$ is equal to $S(n) = \Omega(log \: log \: n)$ because $f(n) \geq cg(n) => f(n) = \Omega(g(n))$ and we can discard $O$ on both sides? $\endgroup$
    – khand
    Nov 6, 2021 at 12:08
  • $\begingroup$ Yes, that’s the idea. $\endgroup$ Nov 6, 2021 at 13:04

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.