43
правки
Изменения
м
→Задача о клике является NP-трудной
===Задача о клике является NP-трудной===
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. Подробное описание сведения содержится в статье [[Сведение по Карпу|сведение по Карпу]].
===Задача о клике принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин кликой.
