NP-полнота
Как уже упоминалось, до сих пор неизвестно, является ли класс задач NP\P пустым или нет. Впрочем, можно найти задачи, которые принадлежат к NP и к которым может быть эффективно (за полиномиальное время) сведена любая задача из NP. Такие задачи назовем NP-полными, а класс таких задач назовем NP-complete
(или, короче, NPC). Очевидно, для класса NPC справедливо высказывание
Р ¹ NP Þ NP-complete Ç Р = Æ.
Естественно, если существует задача Q в NP, которая не входит в Р, то NP-полные задачи не могут быть в Р, поскольку Q всегда за полиномиальное время может быть сведена к NP-полной задаче. Покажем теперь, что класс NPC не пуст, задав специальные NP-полные задачи.