A lower bound to palindrome recognition by probabilistic Turing machines
Andrew Chi-Chih Yao · 1977
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.