Участник:StasFomin/Решения задач/Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/k-подсемейство множеств - NPC — различия между версиями

Версия 16:10, 11 октября 2020

• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/k-подсемейство множеств - NPC

Сведем задачу о клике к данной задаче.

Пусть дан граф , требуется найти в нем клику размера . Как известно, это NP-полная задача. Рассмотрим теперь граф --- дополнение графа , т.е. граф с тем же множеством вершин, и вершины в нем смежны тогда и только тогда, когда они не смежны в . Пронумеруем ребра графа числами от до , а вершины --- числами от до . Теперь каждой вершине графа поставим в соответствие множество натуральных чисел , в котором хранится, во-первых, номер вершины , а во вторых, номера всех ребер, которые инцидентны вершине .

По построению множества и имеют непустое пересечение тогда и только тогда, когда вершины и смежны в графе . Пусть в семействе множеств существует подсемейство из попарно непересекающихся подмножеств . Тогда в графе вершины попарно несмежны. Тогда в графе вершины попарно смежны, т.е. в графе найдена клика размера .

Таким образом, мы полиномиально (система множеств строится за время ) свели NP-полную задачу о клике к данной задаче. Значит, данная задача NP-полна.