17. Характеристики сложности вычислений

В общей теории алгоритмов изучается лишь принципиальная возможность алгоритмического решения задачи. При рассмотрении конкретных задач не обращается внимание на ресурсы времени и памяти для соответствующих им разрешающих алгоритмов. Однако нетрудно понять, что принципиальная возможность алгоритмического решения задачи еще не означает, что оно может быть практически получено. Поэтому возникает потребность уточнить понятие алгоритмической разрешимости, введя характеристики сложности алгоритмов, позволяющие судить об их практической реализуемости. Выше было установлено, что различные алгоритмические модели приводят к одному и тому же классу алгоритмически вычислимых функций. В то же время ясно, что выбор алгоритмической модели, реализующей алгоритмы, существенно влияет на сложность вычислений. Утверждения о трудоемкости вычислений, вообще говоря, не сохраняются при изменении алгоритмической модели. Однако имеется ряд фактов, которые не зависят от вычислительной модели и относятся к так называемой машинно-независимой теории сложности.

Введем необходимые определения, отправляясь от машины Тьюринга в качестве модели вычислительного устройства. Пусть машина Тьюринга Т вычисляет словарную функцию F(X). Определим функцию TT(X), равную числу шагов машины Т, выполненному при вычислении F(X), если F(X) определено. Если F(X) не определено, то значение TT(X) считается неопределенным. Функция TT(X) называется Временной сложностью.

Активной зоной при работе машины Т на слове Х называется множество всех ячеек ленты, которые содержат непустые символы, либо посещались в процессе вычисления F(X) головкой машины Т. Определим функцию ST(X), равную длине активной зоны при работе машины Т на слове Х, если F(X) определено. Если F(X) не определено, то значение ST(X) считается неопределенным. Функция ST(X) называется Емкостной (ленточной) Сложностью.

Теорема 17.1. Пусть машина Тьюринга Т имеет внешний и внутренний алфавиты мощности K и R соответственно. Тогда для функций сложности TT(X) и ST(X) справедливы оценки

ST(X) £ |x| + TT(X),

TT(X) £ R(ST(X))2 .

Доказательство. В начальный момент на ленте записано слово Х длины |X|. На каждом шаге активной становится не более одной новой ячейки, поэтому ST(X) £ |X| + TT(X). Найдем теперь число различных конфигураций , с активной зоной , не превосходящей фиксированной величины S. Имеется вариантов записи на ленте, вариантов выбора положения головки и S вариантов для значения длины конфигурации К. Таким образом, число рассматриваемых конфигураций не превосходит Rs2KS. Далее, если в процессе работы машины встретятся две одинаковые конфигурации, то машина зациклится, поскольку конфигурация однозначно определеяет следующую за ней. Значит, если машина в процессе работы использует зону ST(X), то число ее шагов не превосходит числа различных конфигураций с зоной, не превышающей ST(X). В итоге получаем неравенство TT(X) £ £ R(ST(X))2, и теорема доказана.

Введенные функции ST(X) и TT(X) являются словарными. Удобно ввести для рассмотрения функции натурального аргумента, положив

, .

Они также называются функциями временной и емкостной сложности (по худшему случаю). Поведение этих функций в пределе при увеличении размера задачи N называется Асимптотичской Временной (соответственно — емкостной) Сложностью. Для конкретных задач находятся, как правило, асимптотические функции сложности.

Заметим, что для введенных функций ST(X) и TT(X) выполнены свойства:

1) , где  — область определения функции G(X), FT — функция, вычисляема машиной Т;

2) предикат P(X, Y), определенный соотношением P(X, Y) = = (TT(X) = Y) — разрешим. Аналогичное свойство справедливо для функции ST(X).

Подобным образом можно определить функции сложности вычисления на машине МПД. Пусть Р — программа МПД. Обозначим через TP(X) функцию, определенную условием , т. е. это есть число шагов вычисления на начальной конфигурации Х по программе Р, если вычисление заканчивается, и не определено в противном случае. Ясно, что для введенной функции TP(X) также выполнены условия 1) и 2).

Дадим теперь определение абстрактной меры вычисления (для одноместных) числовых функций. Пусть F0(X), F1(X), …, FN(X), … — нумерация одноместных частично рекурсивных функций. Мерой вычислительной сложности Называется любое семейство функций Ф0(X), Ф1(X), …, ФN(X), …, обладающее свойствами:

;

Предикат P(X, Y) = (ФI(X) = Y) — разрешим .

Примером меры вычислительной сложности будет, например, семейство функций ФI(X), , где ФI(X) — максимальное число, содержащееся в регистре МПД за все время вычисления РI(X), если РI(X)¯, и не определено в противном случае.

В дальнейшем основное внимание будет уделено сложности тьюринговых вычислений.

Рассмотрим вопрос о верхней границе сложности вычислений, который формулируется так: существует ли такая общерекурсивная функция H(X), что для любой вычислимой функции F(X) найдется машина Тьюринга, для которой TT(X) £ H(X) (соответственно ST(X) £ H(X) там, где значения TT(X) определены).

Если допустить, что значения F(X) могут быть сколь угодно большими, то ответ отрицателен, так как на запись ответа может понадобиться тактов больше, чем H(X). Поэтому предположим, что значения F(X) могут быть только 0,1. Если допустить, что F(X) может быть частичной, то ответ также отрицателен, так как из существования такой общерекурсивной функции H(X) следует существование рекурсивного доопределения для любой рекурсивной функции F(X). Действительно, пусть машина Т вычисляет функцию F(X). Для любого Х отсчитываем H(X) тактов, и ести за это время значение F(X) не определено, то полагаем F(X) = 0. Эта алгоритмическая процедура дает рекурсивное доопределение. Но это противоречит теореме 5 параграфа 9.

Будем теперь рассматривать общерекурсивные 0,1-функции F(X). Следующая теорема показывает, что ответ на поставленный вопрос также отрицательный.

Теорема 17.2. Для всякой общерекурсивной функции H(X) существует общерекурсивая 0,1-функция F(X) такая, что для любой машины Тьюринга Т, вычисляющей F(X), существует значение аргумента X = N, при котором TT(N) > H(N).

Доказательство. Рассмотрим нумерацию машин Тьюринга Т0, Т1, …, ТN, … и соответствующую нумерацию частично рекурсивных функций F0(X), F1(X), …, FN(X), … . Определим функцию

.

Функция F(X) вычислима с помощью следующей процедуры: для любого Х находится значение H(X), затем машина TX применяется к конфигурации и считаются такты работы машины TX. Если в течение H(X) тактов TX остановилась в заключительной конфигурации вида (это проверяется просмотром активной зоны, размер которой не превосходит |X| + H(X)), то полагается . В противном случае величина не определена и полагаем F(X) = 0. Если машина TX не остановилась в течение H(X) тактов, то полагаем F(X) = 0. Итак, вычислимость F(X) доказана. Следовательно, существует машина Тьюринга Т, вычисляющая F(X). Пусть ее номер N. Докажем, что выполнено TT(N) > H(N). Если это не так, т. е. TT(N) £ H(N), то поскольку F = FN общерекурсивна и F(N) определено, тогда F(N) =  = . Следовательно, F(N) ¹, и это противоречит тому, что F вычисляется машиной Т, что и требовалось доказать.

Рассмотрим вопрос о существовании сложно вычислимых функций, который формулируется так: существует ли общерекурсивная 0,1-функция F(X), которая на любой машине Тьюринга для всех Х вычисляется за время, превышающее значение наперед заданной функции H(X).

В такой постановке ответ отрицательный, так как вычисление функции F(X) в любом конечном числе точек можно сделать тривиальным, предварительно занеся эти значения в программу машины. Поэтому в поставленном вопросе потребуем, чтобы нужная оценка выполнялась при всех Х, кроме конечного числа значений.

Теорема 17.3. Для всякой общерекурсивной функции H(X) существует общерекурсивная 0,1-функция F(X) и такая, что для любой машины Т, вычисляющей F(X), существует Х0 такое, что выполнено TT(X) > H(X) при всех X ³ Х0.

Доказательство. Нужную функцию F(X) и вспомогательную функцию будем строить последовательно при Х = 0, 1, 2, … .

Х = 0. Если и определено, то полагаем =, . В противном случае полагаем , не определено.

Х = N > 0. Пусть значения F(X) определены при всех X < N и определены значения . Для нахождения F(N) поступаем следующим образом:

Проверяем выполнимость неравенств , , …, . Для всех , для которых выполнены оба условия

А) ;

Б) FK(N) определено,

Находим наименьшее, которое не является значением функции p. Если такое число есть (обозначим его K0), то полагаем

и .

Если таких чисел K нет, либо все К уже являются значениями функции p, то считаем, что значение p(N) не определено и .

Легко убедиться, что функция F вычислима, всюду определена и принимает значения 0, 1. Функция p(X) принимает различные значения и p(X) £ X.

Пусть Т — произвольная машина, вычисляющая F, и I — номер машины Т. Докажем, что выполнено при всех Х, начиная с некоторого X0.

Пусть это неравенство нарушается для бесконечного числа значений Х. Пусть N1, N2, N3, … такие значения Х, что I ³ N1 > N2 > > N3 > … . Покажем, что по крайней мере в одном из чисел N1, N2, …, NI, NI+1, функция p принимает значение I. Имеем в точках N1, N2, …, NI, NI+1 неравенства и определено. Если значение I не принимается функцией p в точках N1, N2, …, NI, то либо p(X) = I было ранее, что невозможно, так как N1 — первое, начиная с I число, для которого , либо функция p принимала значения, меньшие I. Таких значений I штук и при N £ NI все они являются значениями p (так как значения p различны). Тогда в точке NI+1 функция p принимает значение I. Это значит, согласно определению функции F, что F ¹ FI, т. е. машина Т не вычисляет FI. Полученное противоречие доказывает теорему.

Выше была определена сложность конкретного алгоритма, вычисляющего некоторую функцию F. Рассмотрим вопрос: можно ли определить сложность вычислимой функции как сложность наилучшего алгоритма, вычисляющего ее? Приведем без доказательства результат М. Блюма, показывающий, что, вообще говоря, этого сделать нельзя. Существуют функции, допускающие убыстрение всюду, за исключением конечного числа точек.

Теорема 17.4. Для любой общерекурсивной функции R(X) существует общерекурсивная 0,1-функция F(X) такая, что для любой машины МI, вычисляющей F(X), существует машина МJ, также вычисляющая F(X), что для всех Х, начиная с некоторого, выполнено .

Обсудим некоторые следствия из данного результата.

1. Если взять R(X) = 2Х, то существует функция F(X) со свойством: если она допускает вычисление со сложностью T(X), то она допускает вычисление со сложностью T’(X), причем T(X) > или T’(X) < log T(X). Убыстренное вычисление снова допускает убыстрение-вычисление со сложностью T’’(X), где T’’(X) < log T’(X) < < loglog T(X) и т. д. (т. е. неравенства выполняются при всех Х, начиная с некоторого).

2. Пусть мы реализуем работу любой машины М со скоростью 1 шаг/с и переходим к реализации со скоростью 1010 шаг/с. Тогда вычисление на машине МI , требующее TI(X) секунд при старой реализации, требует секунд при новой реализации. Рассмотрим функцию F, определяемую теоремой об ускорении при R(X) = 1010 X. Пусть F вычисляется МI. Тогда существует МJ такая, что 1010 TJ(X) < TI(X), начиная с некоторого X0 или . Значит, для всех X, начиная с некоторого, старая реализация вычисления машины МJ лучше, чем новая реализация машины МI, т. е. более быстрая реализация вычислений не имеет преимуществ перед медленной реализацией для почти всех входов (для некоторых функций).

< Предыдущая		Следующая >