Я понимаю, что 2 SAT можно решить за полиномиальное время, обнаружив сильно связанные компоненты.Что делать с 3SAT?

Question

В случае 3SAT вместо того, чтобы получить 2 значения для одного предложения, мы получили бы 12 (3C2 * 2 * 2), возможно, и сформировали бы график 12-метровых ребер, когда m - это количество предложений в 3 CNF и мы все еще можем узнать Сильно Связанные Компоненты в этом результирующем графе. Что не так в этом утверждении, которое делает 3 SAT проблемой P? например.

(a+b) = (-a->b).(-b->a)
(a+b+c) = (-a->(b+c)).(-(b+c)->a).....4 more like this
        = (-a ->((-b->c).(-c->b)))....2 for each like this

Answer 1

К сожалению, 3-SAT нельзя выразить в 2-SAT, поэтому оно не может быть таким простым, как в 2-SAT.

Однако существует много работ, связанных с поиском алгоритма полиномиального времени для 3-SAT. Идея состоит в том, чтобы найти критерии, которые могут сделать экземпляр 3-SAT «Отслеживаемым фиксированным параметром» (FPT).

Я могу порекомендовать вам статью Об трактуемых параметризациях SAT с фиксированными параметрами , написанную Стефаном Шейдером, где есть отрывок о том, как рассматривать экземпляр SAT в виде графика и искать параметр в графике, чтобы сделать SAT проблема отслеживается.

Вы можете найти больше информации о FPT здесь: https://en.wikipedia.org/wiki/Parameterized_complexity