CODEWITHSUNDEEP
satisfiabilitycnfsat-solvershorn
noctua
noctua

Reputation: 135

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?

Upvotes: 0

Views: 831

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11324

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).

Upvotes: 1

Related Questions