Сложностные задачи теории вычислений

В статье дан обзор современного состояния теории сложности вычислений и ее приложений. Работа состоит из трех глав. В первой главе изложены результаты, опирающиеся на методы общей теории вычислимости. В их числе – общие свойства характеристик сложности, экспоненциальные и более высокие нижние оценки для конкретных задач, классификации задач по сводимости. Во второй главе рассмотрена сложность конкретных задач, для которых удалось построить алгоритмы с нетривиальными верхними оценками временной сложности. Среди этих задач – идентификация подслов данного слова, задачи на графах, геометрические задачи, решение различных уравнений и др. Третья глава посвящена нетривиальным нижним оценкам сложности конкретных задач при решении их на “ограниченных” вычислительных моделях; среди последних – машины Тьюринга, неветвящиеся программы и другие.
Библ. 385 назв.