Итак, какой же практический смысл имеет изучение теории сложности и классификация задач с точки зрения NP-полноты? Ответ очевиден — зачастую гораздо разумнее и эффективнее найти доказательство того, что рассматриваемая задача принадлежит к классу NP-полных, и в соответствие с этим заняться поиском достаточно точных приближенных алгоритмов, нежели безрезультатно тратить время на отыскание полиномиальных алгоритмов ее решения. Ясно, что именно NP-полные задачи играют здесь центральную роль — дело в том, что полиномиальное время является, хоть и первым, но достаточно хорошим приближением понятия «практической разрешимости задачи».
Однако существует немало других интересных книг по данной тематике, заслуживающих пристального внимания со стороны читателя. Среди них хотелось бы выделить, где можно найти большое разнообразие NP-полных задач из самых различных областей. Читателям, желающим подробнее ознакомиться с теорией сложности, на мой взгляд, будет интересен подробный курс лекций, глубоко освещающий данную тематику
Библиографический список
1. Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи» М.: Мир 1982-466 стр.
2. Иванова А.П. «Введение в прикладное программирование. Модели и вычислительные алгоритмы» М.: Физматлит 2002 г.
3. Перепелица В.А. «Асимптотически подход и решение некоторых экстремальных задач на графах. Проблемы кибернетики » М.: Наука, 1973 г.
4. А.В. Яковлев, А.А. Безбогов, В.В. Родин, В.Н.Шамкин, КРИПТОГРАФИЧЕСКАЯЗАЩИТА ИНФОРМАЦИИ
5. Еремеев А.В., Романова А.А., Сервах В.В., Чаухан С.С. Приближенное решение одной задачи управления поставками // Дискретн. анализ и исслед. операций. Серия 2. 2006. Т. 13, № 1. С. 27–39.