Теория вычислительной сложности

В теории вычислительной сложности формируется пара , составленная из алгоритма А, предназначенного для решения системы задач S и , в частности, конкретной (индивидуальной) задачи s из семейства S.

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

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

Для оценки эффективности алгоритма А на семействе задач S в теории вычислительной сложности используется верхняя оценка сигнализирующей времени

(17)

а для выбора алгоритма из заданного набора {A}, наиболее эффективного для решения задач S, минимальная оценка

(18)

Помимо сигнализирующей времени формируют следующие функции сложности:

сигнализирующая ёмкости - число ячеек оперативной памяти, необходимых для решения задачи sS алгоритмом А;

сигнализирующая колебаний (поворотов) - количество циклов в программе для реальной ЭВМ, которые изменяют типовую последовательность вычислений;

сигнализирующая режима - число обращений к долговременным запоминающим устройствам.

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

Различают задачи полиномиальной и экспоненциальной сложности:

O(n²), O(n³)

O(aⁿ), O(bn^logn) и т.п.

Для (1) относятся задачи а) перемножения двух матриц порядка n; б) о кратяайшем маршруте на графе с n вершинами.

Для (2) - экстремальные задачи комбинаторного типа и задачи теории графов.

Задачи, для решения которых разработаны алгоритмы полиномиальной сложности, относятся к классу P-сложных задач.

Задачи, для решения которых разработаны алгоритмы экспоненциальной сложности, относятся к классу NP-полных задач.

Класс задач P-сложности является подклассом NP-сложных задач.

В книге Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи», Мир, 1982

предложена классификация задач принятия решений.

Приведён список 300 NP-сложных задач. Этот подкласс характерен тем, что, если хотя бы для одной из них будет разработан алгоритм решения полиномиальной сложности, то аналогичные алгоритмы можно получить для всех NP-полных задач.

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