Особые случаи SAT и соответствующих #SAT со сложностью больше всего O (n ^ 2) И которые имеют эффективные алгоритмы для генерации экземпляров?

Question

Мне интересно узнать о частных случаях проблем булевой выполнимости, которые, как известно, являются полиномиальными (или, более реалистично, O (N ^ 2)). Эти случаи также должны иметь эффективный алгоритм для фактического генерирования всех удовлетворительных экземпляров, где под эффективным я имею в виду, что требуется O (N #SAT) для генерации последовательности всех экземпляров. Возможно, что второе условие подразумевает первое, но оно мне не ясно.

Тривиальный пример: 1SAT:)

Тривиальный пример: 2SAT с «цепочками» предложений, так что граф, соединяющий переменные с предложениями, представляет собой строку.

Есть ли где-нибудь еще список? Спасибо.

Answer 1

С Сложность проблем удовлетворенности Шефера:

Мы показываем, что (при условии P! = NP) SAT (S) разрешимо за полиномиальное время, только если хотя бывыполняется одно из следующих условий:

(a) Каждое отношение в S удовлетворяется, когда все переменные равны 0.

(b) Каждое отношение в S удовлетворяется, когда все переменные равны 1.

(c) Каждое отношение в S определяется формулой CNF, в которой каждый конъюнкт имеет не более одной отрицательной переменной.

(d) Каждое отношение в S определяется формулой CNF, в которойкаждый конъюнкт имеет не более одной неотмеченной переменной.

(e) Каждое отношение в S определяется формулой CNF, имеющей не более 2 литералов в каждом конъюнкте.

(f) Каждое отношение в Sявляется набором решений системы линейных уравнений над двухэлементным полем {0,1}.

Первые два разрешимы O (1), следующие три O (n) ипоследний O (n ^ 3) (я думаю).Итак, нужные вам экземпляры SAT находятся в одном из первых пяти классов.