Конспект установочных лекций по комплексному курсу Информатика, Теория информации

NP-полнота


Как уже упоминалось, до сих пор неизвестно, является ли класс задач NP\P пустым или нет. Впрочем, можно найти задачи, которые принадлежат к NP и к которым может быть эффективно (за полиномиальное время) сведена любая задача из NP. Такие задачи назовем NP-полными, а класс таких задач назовем NP-complete

(или, короче, NPC). Очевидно, для класса NPC справедливо высказывание

Р ¹ NP Þ NP-complete  Ç  Р = Æ.

Естественно, если существует задача Q в NP, которая не входит в Р, то NP-полные задачи не могут быть в Р, поскольку Q всегда за полиномиальное время может быть сведена к NP-полной задаче. Покажем теперь, что класс NPC не пуст, задав специальные  NP-полные задачи.



Содержание раздела