On converting CNF to DNF
Peter Bro Miltersen
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 , denotes the minimum number of clauses in a CNF for ; similarly, denotes the minimum number of terms in a DNF for . For , let be the maximum for a function with . We show that there are constants and , such that for all large and all , we have
In particular, when is the polynomial , we get .