CNF против рога удовлетворенности

Я знаю, что легче доказать, выполнима ли формула рога. Мой вопрос: почему с формулой рога легче, чем с обычным CNF?

Источник

1 ответ

Решение

Наличие или отсутствие выполнимости по Хорну может быть показано в линейном времени. Вот хорошее введение с некоторыми примерами. Решение может быть найдено путем распространения единицы без возврата.

Псевдокод из заметки лекции Университета Беркли:

Удовлетворенность общими выражениями CNF является классической NP-полной задачей. Не известны алгоритмы полиномиального времени для удовлетворения CNF (кроме случаев, когда P = NP).

Источник
Другие вопросы по тегам