5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Sam Jones Oct 1 '14 at 10:14
  • 2
    $\begingroup$ 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... $\endgroup$ – Smajl Oct 1 '14 at 10:33
  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael Oct 1 '14 at 20:16
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ One more concern: I can have an expanded alphabet looking like this (symbol, counter value) but this alphabet will still be finite and bounded by some constant. If the input string is long enough, I will not have big enough number for the counter, right? $\endgroup$ – Smajl Oct 1 '14 at 14:26
  • $\begingroup$ You are going to store the counter in binary, so the "overlay tape" only needs two or three symbols. $\endgroup$ – Yuval Filmus Oct 1 '14 at 14:28
  • $\begingroup$ I cant imagine how this alphabet would look like... did you mean it like this? <symbol, 001><symbol, 010> etc? $\endgroup$ – Smajl Oct 1 '14 at 14:31
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 1 '14 at 14:33
  • $\begingroup$ Ok, I get that, but I still cannot see how this solves the problem. The alphabet is still finite and the counter has fixed number of digits. The input could be longer than the counter will be able to store. And size of the alphabet, of course, should not depend on the length of the input... I cannot simply add another digit to the counter because the alphabet must be fixed before the input is processed! $\endgroup$ – Smajl Oct 1 '14 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.