ALCOMFT-TR-03-35

Peter Bro Miltersen, Jaikumar Radhakrishnan and Ingo Wegener
On converting CNF to DNF
Århus. Work package 4. November 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 f:{0,1}ⁿ -> {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}ⁿ -> {0,1} with \cnfsize(f) <= m. We show that there are constants c₁,c₂ >= 1 and epsilon > 0, such that for all large n and all m \in [ (1)/(epsilon)n,2^epsilonn], we have \[ 2^n - c_1\fracn\log(m/n) \leq \dnfsize(m,n) \leq 2^n-c_2 \fracn\log(m/n).\] In particular, when m is the polynomial n^c, we get \dnfsize(n^c,n) = 2^{n -theta(c-1n/(log n))}.

Postscript file: ALCOMFT-TR-03-35.ps.gz (180 kb).