BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-77-647
       ENTRY:: June 28, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: A lower bound to palindrome recognition by probabilistic
               Turing machines
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew Chi-Chih
        DATE:: December 1977
       PAGES:: 22
    ABSTRACT:: We call attention to the problem of proving lower bounds on
               probabilistic Turing machine computations. It is shown that
               any probabilisitc Turing machine recognizing the language L =
               {w $\phi$ w | w $\epsilon$ ${{0,1}}^*$} with error $\lambda$
               < 1/2 must take $\Omega$(n log n) time.
       NOTES:: [Adminitrivia V1/Prg/19950628]
         END:: STAN//CS-TR-77-647