On converting CNF to DNF

We study how big the blow-up in size can be when one switches between the CNF and DNF representations of Boolean functions. For a function f: { 0, 1 } n → { 0, 1 }, cnfsize ( f ) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize ( f ) denotes the minimum number of terms in a DNF for f. For 0 ⩽ m ⩽ 2 n - 1, let dnfsize ( m, n ) be the maximum dnfsize ( f ) for a function f: { 0, 1 } n → { 0, 1 } with cnfsize ( f ) ⩽ m. We show that there are constants c 1, c 2 ⩾ 1 and ε > 0, such that for all large n and all m ∈ [ 1 ε n, 2 ε n ], we have 2 n - c 1 ( n / log ( m / n ) ) ⩽ dnfsize ( m, n ) ⩽ 2 n - c 2 ( n / log ( m / n ) ). In particular, when m is the polynomial n c, we get dnfsize ( n c, n ) = 2 n - θ ( c - 1 ( n / log n ) ).

Authors

• Peter Bro Miltersen
• Jaikumar Radhakrishnan
• Ingo Wegener

Keywords

• Circuit size
• Disjunctive normal form
• Conjunctive normal form
• Switching lemma