Время работы алгоритма

На входе длины n наша программа делает примерно 2 * ?(n²) шагов Сложностью по времени на данном входе x называется число шагов, производимых до перехода в состояние q_yes.

Сложностью по времени называется функция T: N > N, где T (n) есть наибольшая сложность по времени для входов длиной n.

Мы используем принцип несжимаемости, известный в алгоритмической теории информации (колмогоровской сложности). Пусть имеется инъективное отображение f: {0,1}ⁿ > {0,1}^*. Тогда найдётся строка x? {0,1}ⁿ, такая что |f (x)|? n. Это легко видно из подсчёта: строк длиной n имеется 2ⁿ, а строк длиной? n имеется 2⁰ +2¹ +· ··+2^n?1 =2ⁿ? 1. То есть, при любом выбранном кодировании среди всех строк длиной n найдется несжимаемая строка, которая кодируется не менее чем n битами. Пусть машина Тьюринга M распознаёт язык палиндромов. В частности, она должна распознавать слова вида x0x^R, где x? {0,1}ⁿ, а x^R — строка x, записанная в обратном порядке.

Рассмотрим «перегородки» между ячейками ленты и последовательности пересечения этих перегородок (последовательности, показывающие, в каком состоянии произошло очередное пересечение перегородки). Существует i-я перегородка, где n? i? 2ⁿ, такая что соответствующая последовательность пересечений S_i = (q₁,…, q_m) имеет длину m? T (x)/n, где T (x) — время работы машины на входе x0x^R, и n = |x|. По числу i и последовательности S_i можно однозначно восстановить x.

Битовое представление S_i будет занимать не более C_M T (x)/n+2 log n, где log n требуется на хранение n и i. По этому описанию другая машина Тьюринга M` может сгенерировать x.

Теперь мы применяем принцип несжимаемости: сложность K (x) = |f (x)| строки x превосходит log n не более чем на константу C_{M`</sub>. Однако среди строк длиной n найдется несжимаемая строка x<sup>*</sup>, такая что K (x<sup>*</sup>)? n. Таким образом, n? K (x <sup>*</sup>)? C<sub>M</sub> T (x<sup>*</sup>)/n + 2 log n + C<sub>M `}. Значит, T (x^*) = ?(n²).