СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ

— мера сложности в теории автоматов, характеризующая процесс вычисления, происходящий в автомате (в отличие от алгоритмов сложности, которая характеризует громоздкость описания алгоритмов). Термин «сложность вычислений» охватывает совокупность матем. понятий, уточняющих интуитивные представления о трудности, длительности, громоздкости и т. п. вычислительного процесса.

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

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

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

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

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

а для будет .

II. Свойства мер и связь между различными мерами для фиксированных классов автоматов. Рассмотрим, напр., класс обычных одноленточных машин Тьюринга. В качестие меры С. в. иозьмем временную сигнализирующую ф-цию t — время работы на аргументе а. Сформулируем некоторые результаты и терминах распознаиаиия (представления) языков (см. Поведение автоматов). Высказыиание «язык распознается за время понимают так: существует машина, распознающая этот язык, для которой временная сигнализирующая ф-ция на словах длины не больше . Если язык распознается за иремя то он распознается за время для всякого Поэтому оценки даются с точностью до С определенного порядка. Может оказаться, что какой-то язык распознается за время, по порядку равное , и не распознается за время, по порядку меньше . Тогда наилучшее иозможное для этого языка время вычисления точной иременной сигнализирующей ф-цией). Как отмечено и разделе I, такое бывает не исегда. Для языка, состоящего из симметричных слои, показано, что наилучшее время вычисления имеет порядок Построена серия языкои, точные иременные сигнализирующие ф-ции которых лежат между . Доказано, что между нет точных иременных сигнализирующих ф-ций. Сиязь между временной и емкостной сигнализирующими ф-циями устанаилииает следующая теорема: пусть язык распознается за время . Если то этот язык распознается с емкостной сигнализирующей ф-цией, не большей . Аналогичные и другие вопросы изучались для разных типов машин Тьюринга, машин Минского (машин со счетчиками), автоматои с магазинной памятью (см. Автомат магазинный) и др.

III. Сравнение С. в. на разных типах автоматов и для разных типов вычислений. Оценки сложности моделирования одних типов автоматов другими. Рассмотрим, как меняется С. и. при переходе от класса аитоматов к классу аитоматов обладающему более ограниченными вычисл. средстиами. Если состоит из многоленточных машин Тьюринга, а из одноленточных, и язык распознается автоматом из класса за время , то можно построить автомат из класса который распознает его за время Точнее, для моделироиания шагои работы автомата на автомате потребуется не более шагов.

Если ячейки (элементы) автоматов растущих класса соединены друг с другом таким образом, что для каждого элемента число элементов, находящихся от него на расстоянии , сущестиенно больше той же величины для аитоматои класса , то существует автомат из который нельзя моделировать никаким автомаюм из так, чтобы на моделироиание одного шага работы затрачивалось не более чем фиксироианное число шагов. В качестие можно изять, напр., классы диумерных и одномерных аитоматои Неймана — Чёрча.

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

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

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

V. С. в. конкретных классов ф-ций и языков.

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

Исследуется сложность решения задач вычислительной математики (нахождение корней многочленов, произведения матриц, решение систем линейных уравнений и др.), оцениваемая числом арифм. операций. Ее можно рассматривать как С. в. на машине, среди элементарных команд которой содержатся такие операции. Эта проблематика тесно связана с той, которая изучается в вычисл. математике под названием «методы вычислений».

Большой интерес представляет вопрос о сложности языков, изучаемых в лингвистике математической и в программировании для ЦВМ. Много работ посвящено построению и оценке сложности алгоритмов распознавания (анализа) для класса бесконтекстных языков и некоторых других, интересных как с точки зрения внутр. проблем лингвистики, так и для решения задач, связанных с языками программирования. Для характеристики таких языков используются различные типы автоматов, особенно с магазинной памятью.

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

VI. Приложение понятий и методов теории С. в. для уточнения интуитивных представлений о внутренней и относительной трудности различных проблем. Во многих задачах дискретной математики в связи с нахождением оптим. решения возникает проблема т. н. «полного перебора». Были сделаны попытки уточнить и выяснить это явление в сложностных терминах.

В терминах сложности алгоритмов удается определить класс сложных последовательностей, которые удовлетворяют всем «законам случайности», — так сказать, «абсолютно случайны». Они в некотором смысле очень нерегулярны, трудны для предсказания. В терминах С. в. можно ставить и решать вопрос о том, насколько сложны «относительно случайные» (псевдослучайные) последовательности. Понятие относительной трудности разрешимых множеств (и соответствующих степеней трудности) можно уточнить, налагая на алгоритмы сведения сложностные ограничения. При этом можно получить богатые структуры степеней.

VII. Меры сложности и подходы, учитывающие С. в. и сложность описания алгоритма.

В качестве одной из таких мер рассматривается, напр., произведение числа внутр. состояний машин Тьюринга на сигнализирующую ф-цию. Изучается зависимость сложности записи алгоритмов, вычисляющих конечные последовательности, от времени их работы. При наложении эффективного ограничения на время работы сложность алгоритмов, удовлетворяющих этому ограничению, может резко возрасти. Лит.: Трахтенброт Б. А. Сложность алгоритмов и вычислений. Новосибирск, 1967 [библиогр. с. 255—258]; Фишер П. Многоленточные и бесконечные автоматы. В кн.: Кибернетический сборник. Новая серия, в. 5. М., 1968; Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций. М., 1970. В. Н. Агафонов.