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

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

Чаще всего рассматриваются временные и пространственные характеристики алгоритмич. процессов. Так, для Тьюринга машины М сигнализирующая функция времени (время работы) есть число 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.

Н. В. Петри.

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

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

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

Пусть s - произвольная мера сложности машин Тьюринга. Если U - произвольный эффективно (т. е. алгоритмически) перечнслимый бесконечный подкласс машин Тьюринга, то существует машина Т, принадлежащая U, и существует машина Т' (не обязательно из U).такая, что Т' и Т вычисляют одну и ту же функцию, и сложность Т' значительно меньше, чем сложность Т. Отсюда, в частности, вытекает существование примитивно рекурсивных функций, наименьшая сложность к-рых в примитивно рекурсивной форме (т. е. через схемы примитивной рекурсии) значительно больше, чем их наименьшая сложность в общерекурсивной форме (т. е. через схемы общей рекурсии). Пусть под сложностью нормальных алгорифмов и машин Тьюринга понимаются, соответственно, длина изображения и число внутренних состоянии, Тогда любую функцию алгебры логики от N переменных (см. Булева функция).можно реализовать (см. [3]): а) нормальным алгорифмом в m-буквенном алфавите со сложностью б) машиной Тьюринга с m-буквенным внешним алфавитом со сложностью .

С 60-х гг. 20 в. начато изучение сложности алгоритмов, решающих конечные куски алгоритмически неразрешимых массовых проблем (так наз. ограниченные ал-горитмич. проблемы). А. А. Марков рассмотрел следующую задачу: для любой функции алгебры логики от Nпеременных построить изображение нормального алгорифма в алфавите реализующего данную функцию и имеющего минимальную сложность среди всех таких алгорифмов. Показано (см. [1], [4]), что сложность нормального алгорифма, решающего эту задачу, имеет порядок 2^N. Изучен также вопрос о сложности алгоритмов, решающих для первых пнатуральных чисел проблему вхождения в рекурсивно перечислимое множество (сложность n-кусков рекурсивно перечислимых множеств). Показано, что в случае нормальных алгорифмов эта сложность по порядку не превосходит п что в общем случае эта оценка не может быть понижена. В то же время существуют множества, задаваемые с помощью достаточно простых логич. средств, к-рые имеют сложность n-кусков порядка n. Показано также, что при общерекурснвном ограничении времени работы алгорифмов сложность n-кусков рекурсивно перечислимых множеств может возрастать экспоненциально и по порядку достичь величины п.

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

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

Лит.:[1] Марков А. А., "Изв. АН СССР. Сер. матем.", 1967, т. 31, № 1, с. 168-208; [2] Блюм М., сб. "Проблемы математической логики", М., 1970, с. 423-31; [3] Кузьмин В. А., сб. ((Проблемы кибернетики", 1965, вып. 13, с. 75-96; [4] Петри Н. В., "Докл. АН СССР", 1969, т. 185, № 1, с. 37-39; [5] Звонкий А. К., Левин Л. А., "Успехи матем. наук", 1970, т. 25, вып. 6, с. 85-127.

Я. М. Барздинъ.