6
$\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?

Improve this question
$\endgroup$
3
  • 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
    Commented Oct 1, 2014 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
    Commented Oct 1, 2014 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
    Commented Oct 1, 2014 at 20:16

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
7
  • $\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
    Commented Oct 1, 2014 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
    Commented Oct 1, 2014 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
    Commented Oct 1, 2014 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
    Commented Oct 1, 2014 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
    Commented Oct 1, 2014 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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