Pull to refresh

Сведение с применением «регуляторов»: задача выполнимости

Reading time 5 min
Views 4.8K
Привет, Хаброжители! Мы решили опубликовать отрывок из книги «Алгоритмы: разработка и применение. Классика Computers Science». Задачи SAT и 3-SAT. Допустим, имеется множество X из n булевых переменных x1, ..., xn; каждая переменная может принимать значение 0 или 1 (эквиваленты false и true). Литералом по X называется одна из переменных xi или ее отрицание. Наконец, условием называется обычная дизъюнкция литералов image

А теперь дадим формальное определение присваиванию значений, удовлетворяющих набору условий. Логическим присваиванием для X называется присваивание значения 0 или 1 каждому xi; другими словами, это функция ν: X → {0,1}. Присваивание v неявно задает значение истинности, противоположное xi. Присваивание выполняет условие C, если после него C дает результат 1 по условиям булевой логики; это эквивалентно требованию о том, чтобы по крайней мере один из литералов в C имел значение 1. Присваивание выполняет совокупность условий C1, ..., Ck, если в результате его все Ci дают результат 1; иначе говоря, если в результате его конъюнкция
image
Логическое присваивание ν, которое задает всем трем переменным значение 1, не является выполняющим, потому что с ним не выполняется второе из перечисленных условий; с другой стороны, присваивание ν', которое задает всем переменным значение 0, является выполняющим.

Теперь можно привести формулировку задачи выполнимости, также обозначаемой SAT:
Для заданного множества условий C1, ..., Ck по множеству переменных X = {x1, ..., xn} существует ли выполняющее логическое присваивание?

Существует частный случай SAT, обладающий эквивалентной сложностью, но при этом более понятный; в нем все условия содержат ровно три литерала (соответствующих разным переменным). Назовем эту задачу задачей 3-выполнимости, или 3-SAT:

Для заданного множества условий C1, ..., Ck, каждое из которых имеет длину 3, по множеству переменных X = {x1, ..., xn}, существует ли выполняющее логическое присваивание?

Задачи выполнимости и 3-выполнимости являются фундаментальными задачами комбинаторного поиска; они содержат основные составляющие сложной вычислительной задаче и в предельно упрощенном виде. Требуется принять n независимых решений (присваивания всем xi) так, чтобы выполнить набор ограничений. Существуют разные способы выполнения каждого ограничения по отдельности, но решения придется скомбинировать так, чтобы все ограничения выполнялись одновременно.

Сведение задачи 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.

Следующее сведение базируется на втором представлении экземпляра 3-SAT; мы закодируем его с использованием независимых множеств в графе. Сначала построим граф G = (V, E), состоящий из 3k узлов, сгруппированных в k треугольников, как показано на рис. 8.3. Таким образом, для i = 1, 2, ..., k строятся три вершины vi1, vi2, vi3, соединенные друг с другом ребрами. Каждой вершине присваивается метка; vij помечается j-м литералом из условия Ci экземпляра 3-SAT.

image

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

Конфликты будут кодироваться добавлением новых ребер в граф: каждую пару вершин, метки которых соответствуют конфликтующим литералам, мы соединяем ребром. Приведет ли это к уничтожению всех независимых множеств размера k или такое множество существует? Это зависит от того, можно ли выбрать один узел из каждого треугольника, чтобы при этом не были выбраны конфликтующие пары узлов. Но ведь именно то, что требуется в экземпляре 3-SAT!

Утверждается, что исходный экземпляр задачи 3-SAT выполним в том и только в том случае, если построенный граф G имеет независимое множество с размером не менее k. Во-первых, если экземпляр 3-SAT выполним, то каждый треугольник в графе содержит как минимум один узел, метка которого дает результат 1. Пусть S — множество, состоящее из одного такого узла в каждом треугольнике. Множество S является независимым; если бы между двумя узлами u, v должны были бы конфликтовать; но это невозможно, так как обе они дают результат 1.

И наоборот, предположим, что граф G содержит независимое множество S с размером не менее k. Тогда прежде всего размер S равен точно k, и оно должно со- держать один узел из каждого треугольника. Далее утверждается, что существует логическое присваивание ν для переменных в экземпляре 3-SAT, обладающее тем свойством, что метки всех узлов S дают результат 1. Как же построить такое присваивание ν? Для каждой переменной xi, если ни xi, ни не используется как метка узла в S, мы присваиваем ν(xi) = 1. В противном случае либо xi, либо является меткой узла в S; потому что если бы один узел в S был помечен xi, а другой, то эти два узла были бы соединены ребром, что противоречило бы нашему предположению о том, что S является независимым множеством. Если xi является меткой узла в S, мы присваиваем ν(xi) = 1; в противном случае выполняется присваивание ν(xi) = 0. При таком построении ν все метки узлов в S дают результат 1.

Так как G содержит независимое множество с размером не менее k в том, и только в том случае, если исходный экземпляр 3-SAT был выполнимым, сведение завершено.

Ссылка на обзор самой книги здесь
Tags:
Hubs:
+8
Comments 1
Comments Comments 1

Articles

Information

Website
piter.com
Registered
Founded
Employees
201–500 employees
Location
Россия