Вопрос о NP-полноте проблемы независимых множеств

Question

Я думал, что, доказывая, что проблема P является NP-Complete, мы должны были уменьшить известную проблему NPC до P. Но, глядя на решение проблемы с независимым множеством, кажется, что это не так.

Чтобы доказать, что Независимое множество является NP-полным, вы берете граф G, находите его обратное G ', а затем вычисляете CLIQUE (G'). Но это происходит наоборот: он принимает проблему, я не знаю, если это NPC, а затем сводит ее к проблеме известного NPC.

Вот пример решения .

Что мне здесь не хватает? Разве это не неправильно, потому что он делает это наоборот?

Answer 1

Чтобы доказать, что P является NP-полной, нам нужно показать две вещи:

1. То, что P существует в NP.
2. Что есть алгоритм уменьшения времени, чтобы уменьшить некоторую NP-полную задачу Q до P.

Если мы знаем, что КЛИК находится в NPC, то мы можем легко доказать, что ИС находится в NPC.

1. Мы можем проверить IS тривиально в polytime. Итерируйте вершины, убедитесь, что у каждого есть ребро, не входящее в вариант решения.
2. Теперь нам нужно уменьшить CLIQUE до IS. Учитывая график G и целое число n, для CLIQUE мы хотим проверить, существует ли CLIQUE размера n. Пусть H будет инверсией G. Если вы найдете IS в H размера n, у вас есть КЛИК с размером n в G с теми же вершинами. Мы сократили КЛИК до IS.

Если бы вы сократили IS до CLIQUE, вы бы не доказали, что любой из них находится в NPC, если бы вы не могли уменьшить какую-то другую проблему в NPC до IS.

Answer 2

Я думаю, эта страница может вам помочь http://mlnotes.com/2013/04/29/npc.html