Математическая энциклопедия - алгоритма сложность

описания величина, характеризующая длину описания алгоритма. В зависимости от точной концепции алгоритма А. с. описания уточняется по-разному. Единого достаточно устоявшегося уточнения к настоящему моменту (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.

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

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985