CNF vs Horn Удовлетворительность

Question

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

Answer 1

Наличие или отсутствие Horn satisfiability может отображаться в линейном времени. Here - хорошее введение с некоторыми примерами. Решение можно найти по unit propagation без обратного слежения.

ПСЕВДОКОД из университета Берклиlecture note:

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