1. ## SPACE(3 log n)

If L is in SPACE(3logn) then L is in P.

and

Let TRIPLE = {xxx} Prove that triple is in SPACE(log(n)).

2. I assume that $\displaystyle L$ is a language and we are talking about the complexity of a Turing machine that decides membership in this language.

Suppose a machine $\displaystyle M$ with no input has $\displaystyle n$ states and works on at most $\displaystyle m$ cells. Also, assume that $\displaystyle M$ terminates. How long can it run? If there are $\displaystyle k$ symbols in the tape alphabet, then the number of all possible tapes is $\displaystyle k^m$. Therefore, the number of all possible configurations (state, tape) is $\displaystyle nk^m$. If a machine encounters the same configuration twice, then it will loop forever. Thus, the running time is at most $\displaystyle nk^m$.

Now assume that a machine $\displaystyle M$ with $\displaystyle n$ states decides a language $\displaystyle L$ and uses at most space $\displaystyle 3\log m$ on inputs of length $\displaystyle m$. Let's assume for simplicity that $\displaystyle \log$ is to the base $\displaystyle k$, which is the size of the tape alphabet. Then on an input of size $\displaystyle m$ the running time of $\displaystyle M$ is at most $\displaystyle nk^{3\log_k m}=nm^3$. So the time complexity is polynomial in $\displaystyle m$.

For TRIPLE = {xxx}, do you mean that TRIPLE is a language with a single word? Then I believe it would take constant space and time to decide if a given word is xxx or not, and constant space is also logarithmic.

3. Originally Posted by emakarov
I assume that $\displaystyle L$ is a language and we are talking about the complexity of a Turing machine that decides membership in this language.

Suppose a machine $\displaystyle M$ with no input has $\displaystyle n$ states and works on at most $\displaystyle m$ cells. Also, assume that $\displaystyle M$ terminates. How long can it run? If there are $\displaystyle k$ symbols in the tape alphabet, then the number of all possible tapes is $\displaystyle k^m$. Therefore, the number of all possible configurations (state, tape) is $\displaystyle nk^m$. If a machine encounters the same configuration twice, then it will loop forever. Thus, the running time is at most $\displaystyle nk^m$.

Now assume that a machine $\displaystyle M$ with $\displaystyle n$ states decides a language $\displaystyle L$ and uses at most space $\displaystyle 3\log m$ on inputs of length $\displaystyle m$. Let's assume for simplicity that $\displaystyle \log$ is to the base $\displaystyle k$, which is the size of the tape alphabet. Then on an input of size $\displaystyle m$ the running time of $\displaystyle M$ is at most $\displaystyle nk^{3\log_k m}=nm^3$. So the time complexity is polynomial in $\displaystyle m$.

For TRIPLE = {xxx}, do you mean that TRIPLE is a language with a single word? Then I believe it would take constant space and time to decide if a given word is xxx or not, and constant space is also logarithmic.
Thank you! that was very clear.

By TRIPLE = {xxx} i meant {xxx|x is in Sigma*}, sorry.

4. Proving that some task has a certain complexity is intrinsically a hand-waving activity. Nobody is going to write an actual Turing machine, and even if they did, there is a nontrivial task of proving that the machine behaves as claimed. So, to be good at it one has to belong to an elite society of people who have enough experience and intuition that they mostly give correct answers. Even those people essentially cannot offer a more solid proof than "I can prove that the high-level description of the algorithm has this complexity, and I feel that an implementation in a TM will have this complexity as well".

So I can only offer some thoughts. Suppose that we have enough space to write the size of input in binary (or maybe 1/3 of the size). To check if the input has the form xxx, we can start from the beginning, remember the symbol there and then shift two times by 1/3 of total size, checking after each shift that we see the same symbol. If yes, then we do the same thing with the second symbol, third, etc.

I forgot that talking about logarithmic complexity probably involves a TM where the work tape is separate from the input tape, and the space measure is the size of the work tape only. Otherwise, the machine would not be able to visit each cell of the input -- this requires at least linear space and time.

So, each element of the algorithm (finding the length of the input, division by 3, shift by a given number, etc.) are supposed to work in space $\displaystyle C \log n$ (on work tape) on input of size $\displaystyle n$. This seems plausible because it never attempts to write some portion (say, of size $\displaystyle n/10$) of the input to the work tape.