В чем именно разница между этими двумя NP-полными задачами? Мне кажется, что они оба спрашивают, может ли быть удовлетворена логическая формула (т.е. результат 1), но одна находится в контексте схемы, а другая - просто формулы. Однако нельзя ли написать булеву формулу из логической схемы?
Разница между C-SAT и SAT?
Ответы (1)
Вы правы, они очень близки друг другу. Любая проблема C-SAT может быть представлена как SAT, любая проблема SAT может быть представлена как C-SAT. Возникает вопрос, как наиболее оперативно перевести C-SAT ‹-> SAT. Некоторые задачи лучше представлять как SAT, некоторые из них «выглядят» лучше как C-SAT.
Кроме того, существуют SAT-решатели, которые используют представление схемы внутри, вместо более популярной формы клаузы.
Кроме того, вы можете прочитать этот отличный обзор: M. Бьорк, 2009 г., Успешные методы кодирования SAT
person
CaptainTrunky
schedule
22.05.2017
