Editing Conjunctive normal form (section)

==Computational complexity==
An important set of problems in [[computational complexity theory|computational complexity]] involves finding assignments to the variables of a Boolean formula expressed in conjunctive normal form, such that the formula is true. The ''k''-SAT problem is the problem of finding a satisfying assignment to a Boolean formula expressed in CNF in which each disjunction contains at most ''k'' variables. [[Boolean satisfiability problem|3-SAT]] is [[NP-complete]] (like any other ''k''-SAT problem with ''k''>2) while [[2-satisfiability|2-SAT]] is known to have solutions in [[polynomial time]]. As a consequence,{{refn|since one way to check a CNF for satisfiability is to convert it into a [[Disjunctive normal form|DNF]], the satisfiability of which can be checked in [[Time complexity#Linear time|linear time]]}} the task of converting a formula into a [[Disjunctive normal form|DNF]], preserving satisfiability, is [[NP-hard]]; [[Boolean algebra#Duality principle|dually]], converting into CNF, preserving [[Satisfiability and validity|validity]], is also NP-hard; hence equivalence-preserving conversion into DNF or CNF is again NP-hard.

Typical problems in this case involve formulas in "3CNF": conjunctive normal form with no more than three variables per conjunct. Examples of such formulas encountered in practice can be very large, for example with 100,000 variables and 1,000,000 conjuncts.

A formula in CNF can be converted into an equisatisfiable formula in "''k''CNF" (for ''k''&ge;3) by replacing each conjunct with more than ''k'' variables <math>X_1 \vee \ldots \vee X_k \vee \ldots \vee X_n</math> by two conjuncts <math>X_1 \vee \ldots \vee X_{k-1} \vee Z</math> and <math>\neg Z \vee X_k \lor \ldots \vee X_n</math> with {{mvar|Z}} a new variable, and repeating as often as necessary.