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