On converting CNF to DNF

Abstract

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 epsilon > 0 , such that for all large n and all m in [ 1/epsilon n , 2^{epsilon 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 - theta) (c^{-1} n / log n)}.