Шурыгин В.А. Сложностный метод теории алгоритмов

Оглавление

Предисловие

В математической литературе термин сложность алгоритма используется, по крайней мере, в двух смыслах, которые можно передать словами сложность вычислений, задаваемых алгоритмом, и сложность описания алгоритма. Здесь термин сложность алгоритма используются во втором из названных смыслов; точнее говоря, он обозначает размеры наборов знаков, которыми задаются алгоритмы при определенном способе их записи.

Истоками представленной в этой книге теории следует считать работы А.А.Маркова [2] и А.Н.Колмогорова [4]. Эта теория дает новые подходы к исследованию алгоритмических проблем; появление в ней теорем, относящихся не только к конкретным алгоритмическим проблемам, позволяет считать, что она выходит из стадии первоначального накопления фактов, это оправдывает (если не сказать: делает необходимым) систематическое изложение этой теории или ее основной части, и предлагаемая книга – попытка такого изложения.

В теории сложности алгоритмов объекты изучения – алгоритмы – должны допускать запись в стандартной форме, например, определенной в какой-нибудь из хорошо развитых теорий алгоритмов. Здесь в основу изложения взята теория нормальных алгорифмов А.А.Маркова.

Многие из представленных здесь результатов были опубликованы в изданиях Академии Наук СССР. Почти все заимствованные теоремы здесь даны с иными доказательствами, чем в первоисточниках. Изменения в доказательствах вызваны стремлением изложить весь материал в едином стиле, стремлением показать возможность применения некоторых общих методов теории сложности алгорифмов в исследовании различных по характеру алгорифмических проблем, а также стремлением изложить материал без ссылок на факты, которые могут быть не известны тем читателям, чья узкая специализация не связана с теорией рекурсивных функций; кроме того, заменяя авторские доказательства из первоисточников новыми доказательствами, я исходил также из того, что новые доказательства известных теорем могут представлять определенный интерес. Здесь, за редкими исключениями, нет пометок, указывающих, что та или иная теорема приведена в первоисточнике без доказательства или что приводимое здесь доказательство отличаются от авторского, и ответственность за все приведенные здесь доказательства я беру на себя.

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