# Non-deterministic Turing machine and palindromes

I have to design a Non-deterministic Turing machine that accepts only non-palindromes in $NTime(n\log n)$.

I think this would be easy on a 2-tape DTM. Simply copy the string onto the second tape – $O(n)$ time – and then check both tapes (one from beginning and the second from the end) – $O(n)$ time again.

However, I can't picture how to do such procedure in a non-deterministic TM using only one tape. All the procedures I came up with take $O(n^2)$ steps. How can the non-determinism reduce the running time here?

• If a string is a non-palindrome then it fails to be a palindrome in one (or more) places. Use the non-determinism to guess where this place is. – Sam Jones Oct 1 '14 at 10:14
• Thanks for the tip. That makes sense. But in that case, you will have to pick a symbol on the tape and check it with the appropriate symbol on the other end of the tape. How do you save the position? You cannot save it in a state since the length is variable and you have fixed number of states... – Smajl Oct 1 '14 at 10:33
• Possibilities: 1) Construct a PDA and simulate it with a TM. 2) Construct a 2-tape TM and simulate it with a regular TM. (Both simulations are textbook material.) – Raphael Oct 1 '14 at 20:16

Guess a position $\ell$ and add it to the left of the input. Copy it to the beginning of the tape, on top of the input string (use an expanded alphabet). Now go to position $\ell$, carrying your counter around with you. For each position you move, you need to spend $O(\log n)$ time to copy the counter, but that's fine. Decrementing the counter and comparing it to zero also take only $O(\log n)$. Once at position $\ell$, remember the symbol there, and go back to the beginning. Now move your counter all the way to the other end of the string, and count $\ell$ positions from there. Compare the symbol you find to the one you remember.
• It is enough for each cell in the overlay tape to contain one bit. The counter occupies $O(\log n)$ cells on the overlay tape, which keep moving as you move along the input tape. – Yuval Filmus Oct 1 '14 at 14:33