One tape nondeterministic Turing machine accepting non-palindromes I have to design a nondeterministic one tape Turing machine that accepts only non-palindromes in $O(n \log n)$ time.
My best shot was only in $O(n^2)$ time. How can I use the properties of NTM on a single tape to find a faster solution?
Hint: to prove that a string $x_1x_2\cdots x_n$ is not a palindrome, we only need a value $i$ for which $x_i\neq x_{n+1-i}$.