|Abstract of Paper|
On converting CNF to DNF
by Peter Bro Miltersen, Jaikumar Radhakrishnan and Ingo Wegener
The best-known representations of boolean functions f are those as disjunctions of terms (DNFs) and as conjunctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of clauses in a CNF representing f. This leads to the problem of estimating the largest gap between CNF size and DNF size. More precisely, what is the largest possible DNF size of a function f with polynomial CNF size? We show the answer to be $2^(n-Theta(n/log n))$.