Talk:2-satisfiability

From Wikipedia, the free encyclopedia

[edit] Contradiction

The article SAT solver states:

SAT is easier if the formulas are restricted to those in disjunctive normal form, that is, they are disjunction (OR) of terms, where each term is a conjunction (AND) of literals (possibly negated variables).

which is clearly in direct contradiction with the intro to this page, which insists on CNF! Could someone please fix? linas (talk) 17:36, 31 March 2008 (UTC)

It is not a contradiction. Sat in disjunctive normal form is trivial: each term gives a satisfying assignment. Sat in conjunctive normal form is, in general, hard, but 2-sat is an easier (though not as trivial as DNF) special case. —David Eppstein (talk) 17:40, 31 March 2008 (UTC)