Skip to main content
Computer Science

Return to Question

added 11 characters in body; edited title
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

1-Tape Non-deterministic One tape nondeterministic Turing machine andaccepting non-palindromes

I have to design a Non-deterministic 1-Tapenondeterministic one tape Turing machine that accepts only non-palindromes in O (n log n)$O(n \log n)$ time.

But myMy best shot was only in O(n^2)$O(n^2)$ time. How can I use the properties of NTM on a single tape to find a faster solution?

1-Tape Non-deterministic Turing machine and non-palindromes

I have to design a Non-deterministic 1-Tape Turing machine that accepts only non-palindromes in O (n log n).

But my best shot was only in O(n^2). How can I use the properties of NTM on a single tape to find a faster solution?

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?

Source Link
Erkan Turan
Erkan Turan
  • 21
  • 1

1-Tape Non-deterministic Turing machine and non-palindromes

I have to design a Non-deterministic 1-Tape Turing machine that accepts only non-palindromes in O (n log n).

But my best shot was only in O(n^2). How can I use the properties of NTM on a single tape to find a faster solution?