Классификация неразрешимых/пролетающих вариантов удовлетворенности

Question

Недавно я нашел в статье [1] специальную симметричную версию SAT под названием 2/2/4-сат. Анкет Но есть много $ text {np} $-полные варианты, например: Монотон NAE-3SAT, Монотон 1-в-3-sat, ...

Некоторые другие варианты подлежат дальности: $ 2 $-$ text {sat} $, planar-nae-$ text {sat} $, ...

Существуют ли документы опроса (или веб-страниц), которые классифицируют все (странные) $ text {SAT} $ ?

---

1. Поиск кратчайшего решения для расширения $ n $ x $ n n $ 15-puzle неразрешимо Д. Ратнер и М. Уостертут (1986)

Answer 1

Классические, хорошо известные результаты

Как упомянуто Стоунтой Зивни по связанному вопросу о CSTheory, Какие проблемы SAT просты?, есть известный результат Шефер с 1978 года (цитируя ответ Зивни):

Если SAT параметризован набором отношений, разрешенных в каком-либо случае, то есть только 6 проведенных случаев: 2-SAT (то есть каждый пункт является бинарным), роговая, двойная аффинная сат (решения для линейных уравнения в Гф(2)), 0-nalid (отношения, удовлетворенные присвоением ALL-0) и 1-классом (отношения, удовлетворенные присвоением ALL-1).

Планар-3sat означает плоскую версию 3sat известно как $ mathcal {np} $-завершить. Видеть D Lichtenstein, Планарные формулы и их использование, 1981. Анкет Непланарная версия 3SAT, конечно, очень известная классическая $ mathcal {np} $-полная проблема.

Не все равных 3SAT (Nae-3sat) $ mathcal {np} $-завершить. Тем не менее, плоская версия его в $ mathcal {p} $, как показано Морет, Планарный NAE3SAT находится в P, 1988.

Более поздние и/или «странные» варианты

$ k $ -colourable monotone nae-3sat

Вот более экзотический или странный вариант, проблема с решением, называемая $ k $ -colourable monotone nae-3sat:

Учитывая монотонное выражение CNF $ phi $ с тремя различными переменными в каждом пункте, так что соответствующий график ограничений $ g ( phi) $ является K-Clourable, выражение $ phi $ не совсем условное?

Здесь соответствующий график ограничений $ g ( phi) $ - простой неисправный график, связанный с $ phi $ следующим образом: каждая переменная $ phi $ является вершиной в $ g $, а две вершины имеют преимущество между ними Iff Они появляются в некотором пункте вместе.

Для $ k = 4 $ проблема в $ mathcal {p} $. Для $ k = 5 $ Однако это $ mathcal {np} $-завершить. Видеть P Jain, на варианте монотонного NAE-3SAT и проблемы без треугольника, 2010.

Линейные варианты CNF

Хотя это не может быть экзотическим или странным, некоторые известные варианты, а именно Nae-sat (не все равных SAT) и Xsat (Точно SAT; именно один буквальный в каждом пункте до 1 и всех других литералов до 0) проблемы удовлетворенности были исследованы в линейный параметр. Положения о линейной формуле пары имеют не более одной общей переменной. Интересно, что статус сложности не следует из теоремы Шефера.

Nae-sat а также Xsat Оставайтесь $ mathcal {np} $-заполните при ограничении линейными формулами. Более того, Nae-sat а также Xsat все еще $ mathcal {np} $-заполнить только на формулах, содержащих только предложения длины не менее $ k $, для каждого положительного фиксированного целого числа $ k geq 3 $. Это $ mathcal {np} $-завершено для монотонных (без положительных литералов) линейных формул. Однако, Nae-sat Полиномиально-временной утечки на точных линейных формулах, где каждая пара различных предложений имеет ровно одну общую переменную.

Некоторые дополнительные аспекты, касающиеся сложности Nae-sat а также Xsat В соответствии с определенными предположениями, вероятно, все еще открыты. Для получения дополнительной информации см., Например, Porschen и Schmidt, на некоторых саб-вариантах над линейными формулами, 2009 а также Porschen et al., Результаты сложности для линейных xsat-problems, 2010.