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

<p>Suppose that you have a TM with $S(n)$ space that recognize palindromes 
$\{x\,0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ (where $x^R$ is the reverse of $x$) 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.</p>

<p>So $T(n)S(n)=\Omega(n^2)$.</p>

CC BY-SA 3.0
2014-03-03T13:51:55.967Z
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
CC BY-SA 3.0
2014-03-03T14:09:36.243Z
I guess it was practically simultaneous.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-03-03T14:30:21.783Z
As you suggested, I accepted Kristoffer's answer since he was a bit earlier... Thanks to both of you!
Bruno
CC BY-SA 3.0
2017-01-16T11:11:51.987Z
$\{x0^{\frac{n}{3}} x^R \mid |x|=|y|=n/3 \}$ looks strange. Better $\{x0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ an annotation that ${}^R$ is the string reverse operator.
miracle173
CC BY-SA 3.0
2014-03-03T13:41:46.603Z
2017-01-16T20:47:49.137Z
2017-01-16T20:47:49.137Z
Marzio De Biasi
<p>In addition to the other answers, it's worth noting that if randomization is allowed, palindromes can be recognized with O(1) space and O(n) time by hashing the left side of the string, hashing the transpose of the right side of the string, and checking if the hashes are equal. It shouldn't be hard to do this on a Turing machine. </p>

CC BY-SA 3.0
2014-03-05T02:58:43.207Z
2014-03-05T02:58:43.207Z
greg
<p>Using crossing sequences or communication complexity it is simple to derive the tradeoff $T(n)S(n) = \Omega(n^2)$ for a <em>sequential</em> Turing machine using time $O(T(n))$ and space $O(S(n))$.</p>

<p>This result was first obtained by Alan Cobham using crossing sequences in the paper <a href="http://dx.doi.org/10.1109/SWAT.1966.30">The recognition problem for the set of perfect squares</a> which appeared at SWAT (later FOCS) 1966.</p>

CC BY-SA 3.0
2014-03-03T13:40:04.823Z
2014-03-03T13:45:55.410Z
2014-03-03T13:45:55.410Z
Kristoffer Arnsfelt Hansen
<p>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. </p>

<p>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?</p>

<cc.complexity-theory><time-complexity><space-complexity><space-time-tradeoff>
How much time to recognize palindromes in logarithmic space?
Bruno
# How much time to recognize palindromes in logarithmic space?

(Asked by: username_0 on 2014-03-03)

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?

**Tags:** cc.complexity-theory, time-complexity, space-complexity, space-time-tradeoff

---

## 3 answers

### Answer by username_2 on 2014-03-03. Score: 23 | Accepted answer

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](http://dx.doi.org/10.1109/SWAT.1966.30) which appeared at SWAT (later FOCS) 1966.


---

### Answer by username_1 on 2014-03-03. Score: 25

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
$\{x\,0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ (where $x^R$ is the reverse of $x$) 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)$.

> **Comments:**
> **username_1**: 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.  
> **username_2**: I guess it was practically simultaneous.  
> **username_0**: As you suggested, I accepted Kristoffer's answer since he was a bit earlier... Thanks to both of you!  
> **username_3**: $\{x0^{\frac{n}{3}} x^R \mid |x|=|y|=n/3 \}$ looks strange. Better $\{x0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ an annotation that ${}^R$ is the string reverse operator.  

---

### Answer by username_4 on 2014-03-05. Score: 3

In addition to the other answers, it's worth noting that if randomization is allowed, palindromes can be recognized with O(1) space and O(n) time by hashing the left side of the string, hashing the transpose of the right side of the string, and checking if the hashes are equal. It shouldn't be hard to do this on a Turing machine.


---

