Сведение задачи 3-SAT к задаче о независимом множестве
А теперь свяжем вычислительную сложность, воплощенную в задачах SAT и 3-SAT, с другой (на первый взгляд) сложностью, представленной поиском независимых множеств и вершинных покрытий в графах, а именно: мы покажем, что 3-SAT ≤P Независимое множество.
Основная трудность в подобных доказательствах очевидна: в задаче 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.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу