satisfiabilitycnfsat-solvershorn

CNF vs Horn Satisfiability

I know that it's easier to prove if a horn-formula is satisfiable. My Question is: Why is it easier with a horn formula rather than a normal CNF?

Solution

  • Presence or absence of Horn satisfiability can be shown in linear time. Here is a good introduction with some examples. The solution can be found by unit propagation without backtracking.

    Pseudocode from a UC Berkeley lecture note:

    enter image description here

    Satisfiability for general CNF expressions is a classic NP-complete problem. No polynomial time algorithms are known for CNF satisfiability (except if P=NP).