Сведение задачи 3-SAT к задаче о независимом множестве

А теперь свяжем вычислительную сложность, воплощенную в  задачах SAT  и 3-SAT, с другой (на первый взгляд) сложностью, представленной поиском независимых множеств и вершинных покрытий в графах, а именно: мы покажем, что 3-SAT ≤P Независимое множество.

Основная трудность в подобных доказательствах очевидна: в задаче 3-SAT речь идет о присваивании значений булевым переменным с учетом ограничений, тогда как задача о независимом множестве направлена на выбор вершин в графе.

Чтобы решить экземпляр задачи 3-SAT  с использованием «черного ящика» для задачи о независимом множестве, необходимо как-то закодировать все эти булевы ограничения в узлах и ребрах графа, чтобы критерий выполнимости соответствовал существованию большого независимого множества.

Этот прием демонстрирует общий принцип проектирования сложных сведений Y ≤P X: построение «регуляторов» из компонентов в задаче X для представления того, что происходит в задаче Y.

(8.8) 3-SAT ≤P Независимое множество.

Доказательство. Имеется «черный ящик» для задачи о независимом множестве; мы хотим решить экземпляр задачи 3-SAT, состоящий из  переменных X = {x1, …, xn} и условий C1, …, Ck.

Чтобы правильно взглянуть на проблему сведения, следует понять, что существуют две концептуально различающиеся точки зрения на экземпляр 3-SAT.

• Первый способ представления экземпляра 3-SAT был предложен ранее: для каждой из n переменных принимается независимое решение 0/1, а успех достигается при достижении одного из трех способов выполнения каждого условия.
• Тот же экземпляр 3-SAT можно представить иначе: нужно выбрать один литерал из каждого условия, а затем найти логическое присваивание, в результате которого все эти литералы дают результат 1 с выполнением всех условий.

Итак, успех достигается в том случае, если вы сможете выбрать литерал из каждого условия так, чтобы никакие два выбранных литерала не «конфликтовали»; мы говорим, что конфликт двух литералов возникает тогда, когда один равен переменной xi, а другой ее отрицанию .

Если удастся избежать конфликтов, мы сможем найти логическое присваивание, в результате которого выбранные литералы из каждого условия дают результат 1.