Полиномиально разрешимые и NP-трудные задачи

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

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

Каждому алгоритму А соотносим функции T_А (L) и V_А (L), где T_А (L) – верхняя оценка количества элементарных операций, а V_А (L) – верхняя оценка размера необходимой памяти при решении задачи с объемом входной информации L.

Будем говорить, что задача Z имеет полиномиальную временную сложность (решается в полиномиальном времени, полиномиально разрешима), если для нее существует решающий алгоритм А* такой, что T_А* (L) ≤ Р ₁(L); здесь Р ₁(L) – некоторый полином от одной переменной L. Задача Z имеет полиномиальную емкостную сложность, если для нее существует решающий алгоритм А' такой, что V_А' (L) ≤ Р ₂(L); здесь Р ₂(L) – некоторый полином от одной переменной L. Отметим следующий очевидный факт: если задача Z имеет полиномиальную временную сложность, то ее емкостная сложность также полиномиальная.

Возможны дальнейшие разбиения классов задач, имеющих полиномиальную временную и емкостную сложность. Так задача Z разрешима в линейном времени, если для нее существует решающий алгоритм А такой, что T_А (L) ≤ СL; задача Z разрешима в квадратичном времени, если для нее существует решающий алгоритм А такой, что T_А (L) ≤ СL ²; здесь и далее в приводимых оценочных неравенствах С обозначает некоторую фиксированную константу.

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

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

Будем говорить, что задача Z имеет экспоненциальную временную сложность (разрешима в экспоненциальном времени, экспоненциально разрешима), если для нее существует решающий алгоритм А такой, что T_А (L) ≤ Са^L; здесь а – некоторая превышающая единицу константа.

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

Объем входной информации по подлежащей решению индивидуальной задаче нередко оценивается числом определяющих эту задачу параметров. Если все параметры – лежащие в фиксированном диапазоне целые числа, то между верхней оценкой показателя L и числом параметров n имеется линейная взаимосвязь. В таком случае можно считать, что характеристики временной и емкостной сложности решающего алгоритма, являются функциями от n.

Различие в возможностях использования полиномиальных и экспоненциальных по вычислительной сложности алгоритмов значительно. Таблица 3.1 позволяет сравнивать скорости роста нескольких типичных полиномиальных и экспоненциальных функций. В клетках этой таблицы представлены продолжительности решения задач при определяемых столбцами значениях параметра n и определяемых строками функциях временной сложности; быстродействие ЭВМ считается равным 10⁶ операций в секунду.

Таблица 3.1

Затраты времени при полиномиальных и экспоненциальных функциях сложности n

Принципиальная разница между алгоритмами полиномиальной и экспоненциальной временной сложности проявляется также при анализе влияния быстродействия ЭВМ на размеры реально решаемых задач. Таблица 3.2 показывает, как увеличатся размеры решаемых за один час задач при увеличении быстродействия ЭВМ в сто и тысячу раз в сравнении с современными машинами.

Таблица 3.2