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))$.