Lower Bound for One-Tape Turing Machine for Recognizing Palindromes
Mathematics Accomplishment | 1966
IBM researcher: Alan Cobham
Where the work was done: IBM T.J. Watson Research Center
What we accomplished: Cobham showed that a one- tape Turing machine could not recognize a palindrome in linear time. In the process he invented the crossing sequence argument, which is one of our key tools in proving lower bounds.
Related links: A. Cobham, Time and Memory Requirements for Machines Which Recognize Squares and Polyndrons Yorktown Heights IBM Research Report RC-1621 (1966). Citation.
Image credit: The graph shows time of solution of problem in milliseconds (msec) vs. problem size, n, for knapsack problems solved by a state-of-the-art specialized algorithm using a 933 MHz Pentium III computer (average of 100 instances, data from:). The fit of the quadratic equation suggests that empirical algorithmic complexity for instances with 50–10,000 variables is O((log n)2) despite having exponential worst-case complexity estimate in theory. By Cngoulimis - Own work, Public Domain