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

Задача допустимости слова языка называется детерминированно-Т(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 и

lim T(n)/n=+?

n®? n

Идея доказательства. Покажем, что для любого числа m Î N можно построить Т-машину М2, которая в случае надобности m знаков в M1 сводит к одному знаку и по меньшей мере m шагов вычислений на M1 заменяет постоянным числом шагов вычислений.

Для этого закодируем в виде состояний М2 информацию, как должны интерпретироваться знаки под головками чтения в смысле M1. Чтобы соответствующее число шагов вычислений M1 можно было свести к меньшему числу шагов М2, машина М2 всегда выполняет следующую схему вычислений.

Сначала М2 анализирует ячейки слева и справа от головки. М2 объединяет в один переход все шаги машины M1, которые могут иметь место, пока не остановится M1 или головка машины M1 пройдет область длины 3*m. Эта область представляется тремя знаками в М2, которые находятся слева, справа от головки и под нею. Благодаря этому объединяются, по крайней мере, m шагов m1. Тем самым М2 моделирует самое большее за 8 шагов вычислений (4 для чтения и 4 для записи) по меньшей мере m шагов M1. Для заданного числа с выберем число m, такое, что с*m > 24.

Каждые Т(n) шагов M1 моделируются с помощью 8*[Т(n)/m] шагов М2; кроме того, М2 должна читать свое входное слово и кодировать его. Это даёт n+[n/m] шагов, так что всего получается меньше чем n+[n/m]+[8T(n)/m]+9 шагов вычислений (поскольку [х]1 < х+1). Так как справедливо limT(n)/n=? n®?, получаем

" d: $ nd Î N: "n³ 2: nd: T(n)/n³d (это значит n £, T(n)/d).

Таким образом, для n³2 и n³nd всегда справедливо n+[n/m]+[8T(n)/m]+9=T(n)[n/T(n)+n/T(n)m+8/m+9/T(n)]£T(n)[1/d+1/md+8/m+9/nd]£ T(n)[8/m+8/d+1/md]

Число d может быть выбрано произвольно. Если мы возьмем d=m+1/8,то имеет место

8/m+8/d+1/md£c.

Это получается из следующего вспомогательного вычисления:

8/m+8/(m+1/8)+1/(mÙ2+1m/8)£24/m£c

Итак, число шагов М^ ограничено числом с*Т(п).

Следствие.

Если LimT(n)/n=? , n>? и c> 0, то справедливо:

DTIME(T(n)) = DTIME(cT(n)) и

NTIME(T(n)) === NTIME(cT(n)).

Предыдущая теорема показывает, что для вопроса о сложности прежде всего интересен порядок функции Т(n).

Важным вопросом является взаимосвязь между DTIME и NTIME, а также между DSPACE и NSPACE. Для ленточной сложности ответ дает теорема Савича (Sawitch). Для формулирования этой теоремы понадобится следующее определение. Функция

S: N > N называется вполне ленточно-конструируемой (конструируемой по памяти), если существует S(n)-ленточно-ограниченная Т-машина, для которой справедливо: для всех чисел nÎ N существует входное слово длины n, для которого Т-машине действительно требуется S(n) ячеек памяти. Аналогично определяется и вполне временно конструируемая функция (конструируемая по времени).

Теорема (по Савичу). Каждая проблема распознавания из NSPACE (S(n)) принадлежит также DSPACE (S(n)2), если S является вполне ленточно-конструируемой и "n Î N: S(n)³ Log(n).

Доказательство. Пусть М1 есть S(n)-лeнтoчнo-oгpaничeннaя Т-машина. Существует константа с Î N, такая, что для всех чисел n Î N справедливо высказывание: Т-машина останавливается самое большее через с^ (при ^=S(n)) шагов, так что существует самое большее с^) конфигураций для входного слова длины n.

Вычисление недетерминированной Т-машины есть трасса (ветвь) в дереве, приведенном на рис. 10.1. При этом для допускаемого слова существует ветвь, на которой нет повторяющихся узлов.

                                            K0

                          å     æ

                                  k1     ….      Kn1

                                        å..æ       å..æ

Содержание раздела