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

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

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

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

Каждому алгоритму А соотносим функции 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⁶ операций в секунду.

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

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