One tape nondeterministic Turing machine accepting non-palindromes

Question

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?

Answer 1

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}$.

Answer 2

The Turing machine maintains a counter on a parallel track (that is, we increase the tape alphabet so that it can accommodate an additional track of information). The Turing machine begins scanning the input, maintaining its current position on the parallel track; the counter is moved along the way so that when considering position $i$, the counter starts at position $i$. At some point, the machine guesses that the current position $i$ is a mismatch, and remembers the symbol at position $i$. It then moves the counter all the way to the of the input, and counts $i$ positions backwards (in the same way, moving the counter along the way). Finally, it verifies that the symbol at position $i$ from the end differs from that at position $i$.

Since the counter is at most $\log n$ bits long, maintaining the counter (including moving it along) takes time $O(\log n)$ for each step. There are $O(n)$ steps, and so the total running time is $O(n\log n)$.