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

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

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

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

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

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

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

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

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

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

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

в случае это приводит к

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

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

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

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

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

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

Н. В. Петри.