Почему 2SAT в P?

55

Я сталкивался с полиномиальным алгоритмом, который решает 2SAT. Мне показалось удивительным, что 2SAT находится в P, где все (или многие другие) экземпляры SAT являются NP-Complete. Что отличает эту проблему? Что делает его таким простым (NL-Complete - даже проще, чем P)?

парень
источник
18
Почему люди думают, что это такой плохой вопрос?
Питер Шор
12
Один интересный аспект заключается в том, что если вы хотите узнать максимальное количество одновременно выполнимых предложений в выражении 2SAT (то есть Max2SAT), то вы снова возвращаетесь к NP-complete.
Шон Харкер
11
Это либо ужасный вопрос, потому что у него нет полезного ответа, либо фантастический вопрос, потому что единственный правильный ответ - «никто не знает».
Джефф
12
Пожалуйста, прочитайте статью "Сложность проблем выполнимости: уточнение теоремы Шефера".
Диего де Эстрада
3
Дорогой парень, тот факт, что 2SAT находится в P, описан почти в каждом стандартном учебнике по сложности, поэтому, когда вы говорите, что только что заметили этот факт, вопрос выглядит так, как будто вы даже не читали стандартный учебник по сложности.
Каве

Ответы:

88

Вот еще одно интуитивное и простенькое объяснение в соответствии с ответом М.Гвинн.

С -SAT вы можете выразить только значения вида , где и - литералы. Точнее, каждый пункт можно понимать как пару значений: и . Если установить истинно, должно быть истинным , а также. Если вы установите в false, должно быть false. Такие последствия просты: нет выбора, у вас есть только2abab2l1l2¬l1l2¬l2l1abba1Возможно, нет места для умножения регистра. Вы можете просто проследить каждую возможную цепочку импликации и посмотреть, извлекаете ли вы когда-либо из и из : если вы делаете для некоторого , то формула 2-SAT неудовлетворительная, в противном случае она выполнима. Это тот случай, когда число возможных цепочек импликации ограничено полиномиальным размером входной формулы.¬lll¬ll

С помощью -SAT вы можете выразить значения в виде , где , и - литералы. Теперь вы в беде: если вы установите истину, то либо или должно быть истинными, но один? Вы должны сделать выбор: у вас есть 2 возможности. Вот где становится возможным умножение падежа и где возникает комбинаторный взрыв.3abcabcabc

Другими словами, -SAT способен выразить наличие более чем одной возможности, в то время как -SAT не имеет такой возможности. Именно такое наличие более чем одной возможности ( возможности в случае -SAT, возможностей в случае -SAT) вызывает типичный комбинаторный взрыв NP-полных задач.3223k1k

Джорджо Камерани
источник
6
Хотелось бы, чтобы я проголосовал за это больше! Намного лучший ответ!
MGwynne
5
@MGwynne: Спасибо за ваш очень добрый комментарий. Не за что, и ваш ответ действительно очень хорош!
Джорджио Камерани
8
Это хороший ответ на хороший вопрос (ИМХО). Как писал Мак Лейн: «Эффективные или хитрые формальные манипуляции вводятся математиками, у которых, несомненно, есть руководящая идея, - но легче сформулировать манипуляции, чем сформулировать идею словами». Прозрачное изложение произведения математики позволяет идеям сиять через проявление манипуляций ". Именно этот вопрос и ответ помогли «идеям просвечивать» (для меня). Спасибо! :)
Джон Сидлес
4
@Джон: Всегда пожалуйста! ;-) Большое спасибо за ваш замечательный и щедрый комментарий, я очень ценю это. Я не мог согласиться со словами Мак Лэйна.
Джорджио Камерани
Согласно ответу Джорджо Камерани, не стоит уменьшать любую проблему NP до 3SAT, если вы вводите больше фиктивных булевых переменных, имеете больше предложений и не имеете ни прибавки, ни прибыли, но более предпочтительно уменьшить это значение до CNF SAT или булевой выполнимости или Вместо этого используйте SAT, потому что в этих задачах вы имеете меньшие логические переменные и меньшие предложения, а это означает, что алгоритмы грубой силы, карты Карно и алгоритм Куайна-МакКласки имеют большую сложность: D.
Прощальный обмен
31

Рассмотрим разрешение по формуле 2-SAT. Любая резольвента имеет размер не более 2 (обратите внимание, что если для предложений длины и соответственно). Количество предложений размера 2 является квадратичным по числу переменных. Следовательно, алгоритм разрешения находится в P.n+m22n,m2nm

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

Попробуйте перевести проблему в 2-SAT. Поскольку у вас не может быть предложений размером 3, вы не можете (в общем) кодировать значения, включающие 3 или более переменных, например, что одна переменная является результатом двоичной операции над двумя другими. Это огромное ограничение.

MGwynne
источник
3
«Вы не можете кодировать такие вещи, как импликация» - IMP-SAT также находится в P (и я думаю, NL)
Макс
8
pq просто . ¬pq
Каве
1
Kaveh, хорошая точка, исправлена ​​сейчас.
MGwynne
Как я уже говорил, когда вы уменьшили свою произвольную проблему NP до логического соответствия или Circuit SAT или CNF SAT, не уменьшайте проблему до 3SAT, потому что проблема становится еще более сложной и сложной с большим количеством логических переменных и выражений. Даже алгоритм разрешения становится менее эффективным в новой задаче!
Прощальный обмен
20

Как говорит Уолтер, пункты 2-САТ имеют особую форму. Это может быть использовано для быстрого поиска решений.

На самом деле существует несколько классов экземпляров SAT, которые могут быть определены за полиномиальное время, и 2-SAT - это только один из этих доступных классов . Есть три основных типа причин для управляемости:

  1. (Структурная управляемость) Любой класс экземпляров SAT, где переменные взаимодействуют в виде дерева, может быть решен за полиномиальное время. Степень полинома зависит от максимальной ширины экземпляров в классе, где ширина показывает, как далеко экземпляр находится от дерева. Точнее, Маркс показал, что если экземпляры имеют ограниченную субмодульную ширину, то класс можно определить за полиномиальное время, используя подход «разделяй и властвуй».

  2. (Возможность изучения языка) Любой класс экземпляров SAT, в которых шаблон переменных «истина-ложь» «хороший», может быть решен за полиномиальное время. Точнее, шаблон литералов определяет язык отношений, и Шефер классифицировал шесть языков, которые приводят к гибкости, каждый со своим собственным алгоритмом. 2-SAT образует один из шести классов Шефера.

  3. (Гибридная трактуемость) Есть также некоторые классы экземпляров, которые не попадают в две другие категории, но которые могут быть решены за полиномиальное время по другим причинам.

    • Даниэль Маркс, Свойства тракторного гиперграфа для удовлетворения ограничений и конъюнктивных запросов , STOC 2010. ( doi , препринт )
    • Томас Дж. Шефер, Сложность проблем выполнимости , STOC 1978. ( doi )
Андраш Саламон
источник
2
Существуют также аргументы, основанные на структуре пространства решений из случайной литературы k-SAT, которые можно использовать для объяснения различий.
Каве
3
@Kaveh: мое описание гибридной управляемости должно было быть достаточно расплывчатым, чтобы охватить такие вещи. Например, для очень особых видов случаев можно привести аргумент об удовлетворяемости, основанный на локальной лемме Ловаша. См. Опрос 1997 года, проведенный Пирсоном и Дживонсом
Саламон,
3
Также обратите внимание, что SAT является частным случаем проблемы удовлетворения ограничений, когда каждая переменная может принимать 2 значения. Когда переменные могут принимать 3 значения, существует 10 доступных языковых классов, классифицированных Андреем Булатовым: cs.sfu.ca/~abulatov/papers/3-el-journal.ps Гибридные классы также более интересны для больших доменов.
Андрас Саламон
10

Если вы понимаете алгоритм для 2SAT, вы уже знаете, почему он в P - это именно то, что демонстрирует алгоритм. Я думаю, что этот комикс иллюстрирует мою точку зрения. Поскольку вы уже знаете, почему 2SAT находится в P, вы, вероятно, хотите знать, почему 2SAT не NP-сложный.

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

Дейв
источник