Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.]

Thanks!

share|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.