Изменения

Перейти к: навигация, поиск

NP-полнота языка CLIQUE

27 байт добавлено, 00:45, 21 декабря 2018
Нет описания правки
===Задача о клике принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин кликой.
 
[[Категория:NP]]
202
правки

Навигация