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

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

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

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

Пусть s — произвольная мера сложности машины Тьюринга. Легко доказать, напр., следующее утверждение. Если U — произвольный эффективно перечислимый класс машин Тьюринга, то существует машина Т, принадлежащая U, и существует машина Т (не обязательно из U) такая, что Т и Т вычисляют одну и ту же ф-цию и сложность Т меньше, чем сложность Т. Сформулируем еще некоторые результаты. Пусть под сложностью нормальных алгорифмов и машин Тьюринга понимается соответственно длина изображения и число внутр. состояний. Тогда любую ф-цию алгебры логики от N переменных можно реализовать нормальным алгорифмом в -буквенном алфавите со сложностью и машиной Тьюринга с -буквенным внеш. алфавитом со сложностью

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

экспоненциально и по порядку достичь величины .

Как видно из приведенных примеров, понятие А. с. в основном используется при уточнении вопроса о том, какова миним. сложность алгоритма, описывающего тот или иной конечный объект. Эту миним. сложность часто наз. сложностью данного конечного объекта. А. Н. Колмогоров предложил другой подход к определению понятия сложности конечного объекта, не зависящий от выбранной концепции алгоритма. Согласно идее Колмогорова, под сложностью объекта следует понимать минимальную длину «программы» , которая позволяет восстановить Точное определение этого понятия зависит от того, какой класс объектов рассматривают и что понимают под «методом программирования». Рассмотрим, напр., класс N двоичных слов. Длину слова обозначим через . Пусть частично рекурсивная ф-ция из N в N. Тогда сложность слова по есть

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

где — сложность по Колмогорову, сложность, выражаемая через длину изображения нормального алгорифма в -буквенном алфавите, сложность, выражаемая числом внутр. состояний машины Тьюринга с -буквенным внеш. алфавитом.

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

Лит.: Кузьмин В. А. Реализация функций алгебры логики автоматами, нормальными алгорифмами и машинами Тьюринга. «Проблемы кибернетики», 1965, в. 13; Марков А. А. О нормальных алгорифмах, связанных с вычислением булевых функций. «Известия АН СССР. Серия математическая», 1967, т. 31, № 1; 3вонкин А. К., Левин Л. А. Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов. «Успехи математических наук», 1970, т. 25, в. 6; Блюм М. Об объеме машин. В кн.: Проблемы математической логики. М., 1970. Я. М. Барздинъ.