# How much time to recognize palindromes in logarithmic space?

It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time algorithm uses a copy of the input, and thus also uses a linear space.

Can we recognize palindromes in linear time of a multitape Turing machine, using only a logarithmic space? More generally, what kind of space-time trade-off is known for palindromes?

-

Using crossing sequences or communication complexity it is simple to derive the tradeoff $T(n)S(n) = \Omega(n^2)$ for a sequential Turing machine using time $O(T(n))$ and space $O(S(n))$.

This result was first obtained by Alan Cobham using crossing sequences in the paper The recognition problem for the set of perfect squares which appeared at SWAT (later FOCS) 1966.

-

You can use the same argument used to prove the $\Omega(n^2)$ time bound on single tape.

Suppose that you have a TM with $S(n)$ space that recognize palindromes $\{x0^{\frac{n}{3}} x^R \mid |x|=|y|=n/3 \}$ in time $T(n)$. When the (input) head crosses the middle $0^{n/3}$ it can carry only $S(n)$ bits of information. So it needs to make $\Omega(n / S(n))$ crosses, and each cross requires $n/3$ time.

So $T(n)S(n)=\Omega(n^2)$.

-
Ops... after writing the answer I saw that Kristoffer already posted the solution. Accepts his answer, I leave mine only because it has a few more details. –  Marzio De Biasi Mar 3 at 13:51
I guess it was practically simultaneous. –  Kristoffer Arnsfelt Hansen Mar 3 at 14:09
As you suggested, I accepted Kristoffer's answer since he was a bit earlier... Thanks to both of you! –  Bruno Mar 3 at 14:30