83
правки
Изменения
Класс NP
,Нет описания правки
==Примеры задач класса NP==
* [[NP-полнота задачи BH1N|Задача о нахождении независимого множества заданного размера в графеBH1N]]. IND* Задача о нахождении клики заданного размера в графе[[NP-полнота задач о вершинном покрытии, клике и независимом множестве|вершинном покрытии, клике и независимом множестве]]. CLIQUE* Задача о нахождении вершинного покрытия заданного размера [[NP-полнота задачи о выполнимости булевой формулы в графе. COVER* Задача о форме КНФ|удовлетворении булевой формулы, заданной в КНФ]]. SAT