Welcome to MathOverflow

Question

3

1

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!

flag	asked Mar 7 2011 at 20:54 LowerBounds 473●2●12

	Yes, it is known. I believe the result is due to Cobham. – aorq Mar 7 2011 at 21:43
	Please correct the misspelling in the title. – JBL Mar 8 2011 at 0:01

Aubrey da Cunha · Answer 1 · 2011-03-07 21:53:01Z UTC

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.

Palinderome in single tape TM in O(n^2)

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.