Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/k-подсемейство множеств - NPC
Материал из DISCOPAL
< Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC | Задачи(перенаправлено с «Даниил Кононенко задача об NP-полноте»)
Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное . Существует ли подсемейство, состоящее из попарно непересекающихся множеств?
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.