MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is known that:

(1) Palindrome can be recognized by two-tape TM in O(N) (2) Palindrome can be recognized by one-tape TM in O(N^2)

Question: do we actually have proof that a one-tape TM can't recognize Palindrome faster than O(N^2)?

[I have some handwavy intuition on why it "must" run back & forth over the tape; but nothing that I can formalize into a proof.]


share|cite|improve this question
Yes, it is known. I believe the result is due to Cobham. – aorq Mar 7 '11 at 21:43
Please correct the misspelling in the title. – JBL Mar 8 '11 at 0:01

The (IMO) easiest way to formalize your intuition is using the language of communication complexity. For example, a proof that palindromes require $\Omega(n^2)$ time on a one-tape, one-head machine is given in "Communication Complexity" by Kushilevitz and Nisan. If all you want is the palindrome proof, you could read chapters 1 and 2 and then jump to chapter 12.

Another popular proof uses the notion of a "crossing sequence". A good reference for that proof is in Lecture 1 of Kozen's "Theory of Computation". Essentially, this is the same as the communication proof, but in different words.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.