Функції складності (сигналізуючі) за часом та за пам’яттю. Теорема про прискорення

В теорії складності обчислень розглядаються обчислювальні задачі чи задачі розпізнавання (аналізу) і досліджуються питання складності розв’язку цих задач на відповідних обчислювальних пристроях. Основний інтерес представляє отримання оцінок складності задач по часу і по пам’яті. Відповідно при розгляді обчислень на машинах Тьюрінга вводяться поняття часової сигналізуючої і сигналізуючої по пам’яті.

Нехай A=(K,Σ, A`, H, q₀, q*)- машина Тьюрінга, що розпізнає мову L(A), де L(A) Σ*. Вважається, що при довільному вхідному слові w є Σ* машина Тьюрінга A, розпочавши роботу в конфігурації q₀w, зупиниться через скінченну кількість кроків (через t_A(w) кроків) і при цьому вона використає l_A(w) комірок робочої стрічки.

При цьому якщо вона зупиниться в кінцевому стані q*, то маємо, що w є Σ*, а в іншому випадку, маємо, що Σ ∉ w. Тепер визначимо для машини Тьюрінга A часову сигналізуючу T_A(x) і сигналізуючи по пам’яті L_A(x).

Покладемо, що

T_A(x)=max{t_A(w)|wє Σ*, |w|<=x}

L_A(x)=max{t_A(w)|wє Σ*, |w|<=x}

Будемо говорити, що задача розпізнавання w є Σ* має верхню (часову) оцінку (в.о.) T(x), якщо існує машина Тьюрінга A, що розпізнає мову L і T_A(x) <= T(x)для всіх натуральних чисел x.

Будемо говорити, що задача розпізнавання w є Σ*має нижню (часову) оцінку (н.о.) T(x), якщо доведено, що для довільної машини Тьюрінга A, що розпізнає мову L виконується співвідношення T (x) <= T_A (x) для всіх натуральних чисел x.

Будемо говорити, що задача розпізнавання w є Σ* має оптимальну (часову) оцінку (о.о.) T(x), якщо функція T(x) є одночасно н.о. і в.о. для цієї задачі.

Теорема про прискорення. Нехай деяка задача розв’язується на МТ A з часовою сигналізуючою T_A (x), де T_A (x) ≥ x². Нехай c - довільне натуральне число і c ≥ 2. Тоді існує МТ B, яка розв’язує ту ж задачу з часовою сигналізуючою T_B(x), де T_B(x) <= 1/c T_A(x) для майже всіх x.

Доведення. Ідея доведення полягає в укрупненні комірок.

Нижня квадратична оцінка тут важлива, бо на перебудову слова в алфавіті Σ потрібний квадратичний час, якщо Σ≥|2|.

Якщо ж вхідні і вихідні слова представлені в однобуквеному алфавіті, то в формулюванні теореми замість нижньої оцінки x² можна взяти оцінку xlog x.