Я понимаю, что 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).

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

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