4
$\begingroup$

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!

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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