АЛГОРИТМА СЛОЖНОСТЬ

Расстановка ударений: АЛГОРИ`ТМА СЛО`ЖНОСТЬ

АЛГОРИТМА СЛОЖНОСТЬ вычислений - функция, дающая числовую оценку трудности (громоздкости) процессов применения алгоритма к исходным данным. Уточнением А. с. вычислений служит понятие сигнализирующей функции (или просто сигнализирующей) - функции, к-рая задается разрешимым отношением между объектами применения алгоритма и натуральными числами и имеет область определения, совпадающую с областью применимости алгоритма.

Чаще всего рассматриваются временные и пространственные характеристики алгоритмич. процессов. Так, для Тьюринга машины М сигнализирующая функция времени (время работы) T_M (P) есть число t тактов работы М при преобразовании исходных слов Р в заключительные; сигнализирующая памяти (или емкости) S_M (Р) определяется как количество ячеек ленты, в к-рых хотя бы раз побывала головка машины при работе над Р. Сходным образом определяются сигнализирующие времени и емкости для нормальных алгорифмов, итеративных сетей, многоголовочных и многоленточных машин Тьюринга и т. п.

Общей особенностью этих двух конкретных типов сигнализирующих является наличие эффективной процедуры, позволяющей для любого алгоритма α (т. е., в частности, для машины Тьюринга, или, точнее, для ее программы), всякого исходного данного х и натурального числа t установить, верно ли, что процесс применения α к х заканчивается со сложностью t. Это обстоятельство положено в основу аксиоматич. построения теории сложности вычислений (см. [1]). Эффективная процедура r наз. мерой вычислений, если она: 1) всегда заканчивается результатом 0 или 1 применительно к тройкам вида < алгоритм, исходное данное, натуральное число >, 2) обладает тем свойством, что для любого алгоритма α и исходного данного х равенство r(α, х, t) = 1 верно не более чем при одном натуральном t, причем такое t существует тогда и только тогда, когда процесс применения α к х заканчивается. Вводится сигнализирующая функция R_α по мере r для α : R_α (x) = t тогда и только тогда, когда r (α, х, r) = 1.

Таким образом, последнее равенство объявляется эквивалентом высказывания «сложность вычисления α на x равна t (по мере r)».

Фиксируя ту или иную меру вычислений, можно ставить задачи о сложности вычисления конкретных функций f, напр. об отыскании алгоритма α, вычисляющего f «лучше других алгоритмов». Однако, как показывает теорема ускорения (см. ниже), подобная постановка не всегда правомерна, и речь может идти скорее об описании скорости роста тех сигнализирующих R_α, для к-рых α вычисляет f [напр., об отыскании верхней и нижней границ сложности вычисления f - двух функций G(x) и g(x) таких, что существует вычисление α функции f, для к-рого R_α (x) ≤ G(x), и для всякого алгоритма β, вычисляющего f, функция R_β в каком-то смысле мажорирует g].

Другим важным направлением в теории сложности вычислений является изучение классов сложности - множеств функций, для к-рых существуют вычисления со сложностью, не превышающей к.-л. границы из множества границ, задающих класс. К этому направлению можно отнести и задачи сравнения сложности вычисления для различных типов алгоритмов (автоматов): переход к иной алгоритмич. системе и мере сложности обычно равносилен рассмотрению подходящей новой меры для исходной концепции алгоритмов.

Укажем нек-рые фундаментальные результаты, не зависящие от выбора меры сложности (в том числе и от выбора конкретного уточнения понятия алгоритма) - лишь бы существовала, напр., эффективная возможность взаимного моделирования алгоритмов рассматриваемого типа и обыкновенных машин Тьюринга. (Для простоты можно представить себе дело так, что речь идет о времени вычисления на машинах Тьюринга натуральнозначных функций натурального аргумента.) Пусть Т и h суть вычислимые натуральнозначные функции (см. Вычислимая функция) на объектах применения алгоритмов, f - функция, определенная на тех же объектах и принимающая лишь два значения (например, 0 и 1).

Во-первых, существуют сколь угодно сложно вычислимые функции. Точнее, для любой функции Т существует вычислимая функция f такая, что для всякого алгоритма α, вычисляющего f, неравенство

неверно лишь в ограниченном числе случаев.

Во-вторых, существуют функции, любое вычисление к-рых в принципе может быть улучшено как угодно сильно. Точнее, имеет место теорема ускорения: для любой функции h (напр., h(t) = 2^t) можно указать вычислимую функцию f такую, что для всякого алгоритма α, вычисляющего f, не может не найтись (здесь эффективная процедура не предполагается) алгоритм β, тоже вычисляющий f и такой, что для всех х (кроме конечного множества)

в случае h(t) = 2^t это приводит к

для почти всех х.

Для мер вычислений, определяющих время работы и объем памяти, заключение теоремы ускорения верно для большинства вычислений в такой форме: если f вычислима со сложностью R(n), то она вычислима и со сложностью R(n)/2 (говорят, что f вычислима со сложностью R(n), если для нек-рого α, вычисляющего ее, R_α (Р) ≤ R(n) для всех слов Р длины n в рассматриваемом алфавите). Поэтому временная и объемная сложности вычислений конкретных функций часто оцениваются с точностью до порядка. Ниже приведены нек-рые конкретные результаты.

Установлено, что время распознавания равенства слов равно (по порядку) n² для машин Тьюринга и нормальных алгорифмов; что всякое свойство слов, распознаваемое на машинах Тьюринга за время, по порядку меньшее функции n log₂ n, распознается и за время n; что вычисления на машинах Тьюринга со временем Т(n) (для Т(n) ≥ n² по порядку) моделируются на машинах Тьюринга с объемом памяти . Доказано, что умножение двух n-разрядных чисел на многоленточных машинах Тьюринга осуществимо за время n^{1 + ε}, но всегда более n по порядку, а итеративные сети могут умножать в реальное время, т. е. i-й младший разряд произведения появляется на выходе с подачей на вход i-x разрядов сомножителей. При моделировании алгоритмич. процессов одного типа с помощью других сложность вычислений, вообще говоря, меняется. Так, уменьшение размерности итеративных сетей приводит к увеличению времени. В то же время замена многоголовочных машин Тьюринга многоленточными не меняет времени вычисления функций. Для многих типов алгоритмов доказывается возможность их моделирования на машинах Тьюринга с полиномиальным (обычно даже квадратичным) возрастанием времени работы и незначительным увеличением объема памяти.

Сложностный подход оказывается полезным при изучении известных иерархий классов общерекурсивных функций, связанных с логическими и алгебраическими их особенностями. Так, напр., примитивно рекурсивные функции оказываются в точности теми функциями, к-рые вычислимы на машинах Тьюринга с объемом памяти, ограниченным определенной функцией. Факты существования достаточно сложно распознаваемых свойств, не зависящие от выбора вычислений, доказываются применением диагонального процесса. Их естественные аналоги были обнаружены для нек-рых разрешимых элементарных теорий и в областях, примыкающих к математич. лингвистике. В то же время для многих практически важных проблем получение хороших нижних границ сопряжено со значительными трудностями. Так, в частности, обстоит дело с задачами переборного характера, к-рые уточняются (в одном из вариантов) как задачи об отыскании среди слов определенной длины слова, удовлетворяющего вычислимому за полиномиальное время условию. Упомянем еще о сложности вычислений на недетерминированных автоматах и автоматах вероятностных. В первом случае речь идет о процессах с элементами произвола, и под сложностью вычислений понимается сложность «самого простого» варианта процесса. Во втором - конкретный ход процесса определяется, помимо программы и аргумента, последовательностью показаний датчика случайных чисел, а результат должен с большой вероятностью совпадать со значением вычисляемой функции. В обоих случаях удается доказать иногда уменьшение сложности вычислений по сравнению с детерминированными процессами.

Качество алгоритмов оценивают не только с точки зрения А. с. вычислений, но и с точки зрения алгоритма сложности описания. Имеются результаты, совмещающие оба подхода.

Лит. : [1] Хартманис Дж., Хопкрофт Дж. Э., «Кибернетический сборник», 1974, вып. 11, с. 131-76.

Н. В. Петри.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.