Я сталкивался с полиномиальным алгоритмом, который решает 2SAT. Мне показалось удивительным, что 2SAT находится в P, где все (или многие другие) экземпляры SAT являются NP-Complete. Что отличает эту проблему? Что делает его таким простым (NL-Complete - даже проще, чем P)?
55
Ответы:
Вот еще одно интуитивное и простенькое объяснение в соответствии с ответом М.Гвинн.
С -SAT вы можете выразить только значения вида , где и - литералы. Точнее, каждый пункт можно понимать как пару значений: и . Если установить истинно, должно быть истинным , а также. Если вы установите в false, должно быть false. Такие последствия просты: нет выбора, у вас есть только2 a⇒b a b 2 l1∨l2 ¬l1⇒l2 ¬l2⇒l1 a b b a 1 Возможно, нет места для умножения регистра. Вы можете просто проследить каждую возможную цепочку импликации и посмотреть, извлекаете ли вы когда-либо из и из : если вы делаете для некоторого , то формула 2-SAT неудовлетворительная, в противном случае она выполнима. Это тот случай, когда число возможных цепочек импликации ограничено полиномиальным размером входной формулы.¬l l l ¬l l
С помощью -SAT вы можете выразить значения в виде , где , и - литералы. Теперь вы в беде: если вы установите истину, то либо или должно быть истинными, но один? Вы должны сделать выбор: у вас есть 2 возможности. Вот где становится возможным умножение падежа и где возникает комбинаторный взрыв.3 a⇒b∨c a b c a b c
Другими словами, -SAT способен выразить наличие более чем одной возможности, в то время как -SAT не имеет такой возможности. Именно такое наличие более чем одной возможности ( возможности в случае -SAT, возможностей в случае -SAT) вызывает типичный комбинаторный взрыв NP-полных задач.3 2 2 3 k−1 k
источник
Рассмотрим разрешение по формуле 2-SAT. Любая резольвента имеет размер не более 2 (обратите внимание, что если для предложений длины и соответственно). Количество предложений размера 2 является квадратичным по числу переменных. Следовательно, алгоритм разрешения находится в P.n+m−2≤2 n,m≤2 n m
Как только вы дойдете до 3-SAT, вы можете получить все большие и большие резольвенты, так что все это становится грушевидным :).
Попробуйте перевести проблему в 2-SAT. Поскольку у вас не может быть предложений размером 3, вы не можете (в общем) кодировать значения, включающие 3 или более переменных, например, что одна переменная является результатом двоичной операции над двумя другими. Это огромное ограничение.
источник
Как говорит Уолтер, пункты 2-САТ имеют особую форму. Это может быть использовано для быстрого поиска решений.
На самом деле существует несколько классов экземпляров SAT, которые могут быть определены за полиномиальное время, и 2-SAT - это только один из этих доступных классов . Есть три основных типа причин для управляемости:
(Структурная управляемость) Любой класс экземпляров SAT, где переменные взаимодействуют в виде дерева, может быть решен за полиномиальное время. Степень полинома зависит от максимальной ширины экземпляров в классе, где ширина показывает, как далеко экземпляр находится от дерева. Точнее, Маркс показал, что если экземпляры имеют ограниченную субмодульную ширину, то класс можно определить за полиномиальное время, используя подход «разделяй и властвуй».
(Возможность изучения языка) Любой класс экземпляров SAT, в которых шаблон переменных «истина-ложь» «хороший», может быть решен за полиномиальное время. Точнее, шаблон литералов определяет язык отношений, и Шефер классифицировал шесть языков, которые приводят к гибкости, каждый со своим собственным алгоритмом. 2-SAT образует один из шести классов Шефера.
(Гибридная трактуемость) Есть также некоторые классы экземпляров, которые не попадают в две другие категории, но которые могут быть решены за полиномиальное время по другим причинам.
источник
Если вы понимаете алгоритм для 2SAT, вы уже знаете, почему он в P - это именно то, что демонстрирует алгоритм. Я думаю, что этот комикс иллюстрирует мою точку зрения. Поскольку вы уже знаете, почему 2SAT находится в P, вы, вероятно, хотите знать, почему 2SAT не NP-сложный.
Чтобы понять, почему 2SAT не является NP-сложным, вы должны подумать о том, как легко свести к нему другие проблемы в NP. Чтобы получить интуитивное понимание этого, посмотрите, как SAT может быть уменьшен до 3SAT, и попробуйте применить те же методы, чтобы уменьшить SAT до 2SAT. 2SAT не так выразителен, как 3SAT и другие варианты SAT.
источник