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!

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .