Использование NP-трудных задач

В настоящее время большое распространение получили криптосистемы с открытыми ключами, характерным свойством которых является то, что знание алгоритма не даёт дополнительных преимуществ при взломе, в отличие от симметричных систем, которые легко взламываются, если знать, по какому базовому правилу они работают. Типичным и самым популярным на данный момент примером системы с открытым ключом является RSA (алгоритм был опубликован в 1977 Ривестом, Шамиром, Эдлманом в MIT). Эта система проста в использовании, и, что более важно, сложна во взломе. Однако до сих пор остаётся открытым вопрос – относится ли задача факторизации, на которой базируется алгоритм RSA, к классу полиномиально разрешимых P или же к классу NP-трудных задач. Задача Р versus NP частично обязана своей значимостью пользующейся успехом теории завершенности NP и частично теории криптографии. Алгоритм удовлетворимости, будучи истинно эффективным алгоритмом по отношению к задаче завершенности NP, с одной стороны, мог бы вызвать к жизни целый ряд полезных алгоритмов для решения многих практических вычислительных задач в промышленности, однако, с другой стороны, такой алгоритм разрушил бы безопасность финансовых и иных сделок, широко использующих Интернет. Не сегодня-завтра может оказаться, что задача факторизации не является NP-трудной и более того, может найтись полиномиальный алгоритм её решения. В этом случае понадобятся совершенно другие методы криптографии. В данной работе я покажу некоторые криптографические методы, основанные на сложности широко известной NP-трудной задачи, задачи о рюкзаке(Knapsack problem)

Заключение

Итак, какой же практический смысл имеет изучение теории сложности и классификация задач с точки зрения NP-полноты? Ответ очевиден — зачастую гораздо разумнее и эффективнее найти доказательство того, что рассматриваемая задача принадлежит к классу NP-полных, и в соответствие с этим заняться поиском достаточно точных приближенных алгоритмов, нежели безрезультатно тратить время на отыскание полиномиальных алгоритмов ее решения. Ясно, что именно NP-полные задачи играют здесь центральную роль — дело в том, что полиномиальное время является, хоть и первым, но достаточно хорошим приближением понятия «практической разрешимости задачи».

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

Библиографический список

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

2. Иванова А.П. «Введение в прикладное программирование. Модели и вычислительные алгоритмы» М.: Физматлит 2002 г.

3. Перепелица В.А. «Асимптотически подход и решение некоторых экстремальных задач на графах. Проблемы кибернетики» М.: Наука, 1973 г.

4. А.В. Яковлев, А.А. Безбогов, В.В. Родин, В.Н.Шамкин, КРИПТОГРАФИЧЕСКАЯЗАЩИТА ИНФОРМАЦИИ

5. Еремеев А.В., Романова А.А., Сервах В.В., Чаухан С.С. Приближенное решение одной задачи управления поставками // Дискретн. анализ и исслед. операций. Серия 2. 2006. Т. 13, № 1. С. 27–39.