3-нфн-сат с вопросом о поворотах

Question

Если вы измените задачу 3-cnf-sat следующим образом:Для каждого c _i , c _i = -x _i1 ИЛИ -x _i2 ИЛИ x _i3 , что означает точноодна из переменных появляется без отрицания.Вам также даются значения (0 или 1) для некоторых (или всех) значений x.Вы должны быть в состоянии решить проблему (найти значения x, которые удовлетворяют задаче или доказать, что она неудовлетворительна) за полиномиальное время.

1. Что такое алгоритм полиномиального времени выполнения, решающий эту проблему?
2. Докажите, что он работает за полиномиальное время.

подсказка: showчто c _i = -x _i1 ИЛИ -x _i2 ИЛИ x _i3 равно c = (x _i1 AND -x _i2 ) -> x _i3

Answer 1

Формулы, которые вы описываете, являются подмножеством формул Хорна.Таким образом, проблема выполнимости не сложнее, чем Выполняемость по Рогу и допускает то же решение за линейное время.