Я пытаюсь выяснить временную сложность машины Тьюринга, которая принимает повторяющиеся строки (ww) в трех случаях: детерминированная машина с 1 лентой, детерминированная машина с 2 лентами и недетерминированная машина с 1 лентой.
Сейчас мои мысли таковы
детерминистическая машина с 1 лентой использует O(n^2) для нахождения средней точки (повторно вычеркивая первый и последний символы во входных данных) и O(n^2) для сравнения первой и второй половин (поскольку она должна идти вперед и назад n/2 раза, каждый раз перебирая n/2 строки),
TM с двумя лентами берет O (n ^ 2), чтобы найти среднюю точку, O (n), чтобы скопировать вторую половину на вторую ленту, затем O (n), чтобы сравнить две половины одновременно,
а недетерминированный угадывает среднюю точку и берет O (n ^ 2), чтобы сравнить две половины.
Тем не менее, я чувствую, что все три случая не должны иметь одинаковую временную сложность O (n ^ 2), поэтому мне было интересно, не являются ли мои рассуждения где-то неверными (или я прав и просто много думаю о проблеме). Любой вклад будет оценен!
