43
правки
Изменения
м
→Доказательство NP-полноты
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о клике является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. Подробное описание сведения содержится в статье [[Сведение по Карпу|сведение по Карпу]].
