On converting CNF to DNF Peter Bro Miltersen Jaikumar Radhakrishnan Ingo Wegener December 2003

### 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 , 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 .

Available as PostScript, PDF, DVI.