CNF-SAT

CNF-SAT ist das SAT-Problem eingeschränkt auf Formeln in Konjunktiver Normalform (KNF).
Eine Formel ist in KNF, wenn sie eine Konjunktion von Klauseln ist, wobei jede Klausel eine Disjunktion von Literalen ist.

Auch CNF-SAT ist NP-vollständig.