Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Временная и ленточная сложность задач


Задача допустимости слова языка называется детерминированно-Т(n)-ограниченной (соответственно, недетерминированно-) по времени (S(n)-ленточно-ограниченной), если существует детерминированная (соответственно, недетерминированная) Т-машина, которая решает эту задачу и является соответствующей Т(n)-ограниченной по времени (S(n)-ленточно-ограниченной) машиной.

Рассмотрим следующие классы задач в зависимости от определенных свойств их сложности.

DSPACE (S(n)): детерминированные 8(n)-ленточно-ограниченные задачи,

NSPACE(S(n)): недетерминированные 8(n)-ленточно-ограниченные

задачи,

DTIME(T(n)): детерминированные Т(n)-ограниченные по времени задачи,

NTI^E(T(n)): недетерминированные Т(n)-ограниченные по времени задачи.

Обратимся к некоторым теоремам, которые показывают, что выбранные меры сложности содержательны (информативны), так как они, в частности, нечувствительны к умножению на константу.

Теорема (сжатие лент). Если задача S(n)-ленточно-ограниченна, то для каждой константы с Î R, где с > 0, эта задача с*S(n)-ленточно-ограниченна. Идея доказательства. Для S(n)-ленточно-ограниченной Т-машины ТМо построить Т-машину TM1, которая по мере необходимости представляет r следующих друг за другом знаков на лентах ТМо (слов длины r) одним знаком на лентах TM1.

Следствие. Для всех вещественных чисел с ÎR, с > 0, справедливо

NSPACE(S(n)) = NSPACE(c*S(n)), так же как и

DSPACE(S(n)) - DSPACE(c*S(n)).

Теорема (редукция числа лент). Если задача может быть решена на S(n)-ленточно-ограниченной Т-машине с k лентами, то она может быть решена и на S(n)-ленточно-ограниченной Т-машине с одной лентой.

Идея доказательства. Пусть М есть S(n)-ленточно-ограниченная Т-машина с k лентами. Можно построить Т-машину, которая k лент машины М моделирует на одной ленте. При этом нужный объем памяти не больше чем k*S(n).

Теорема (линейное увеличение скорости). Если задача, решаемая на Т-машине с k лентами M1, является Т(n)-ограниченной по времени, то эта задача для любого вещественного числа с > 0 также решается на с*Т(n)-ограниченной по времени Т-машине с k лентами М2, если k > 1 и




Содержание  Назад  Вперед