TY - JOUR
AU - Miltersen, Peter Bro
AU - Radhakrishnan, Jaikumar
AU - Wegener, Ingo
PY - 2003/12/11
Y2 - 2023/06/08
TI - On converting CNF to DNF
JF - BRICS Report Series
JA - BRICS
VL - 10
IS - 45
SE - Articles
DO - 10.7146/brics.v10i45.21817
UR - https://tidsskrift.dk/brics/article/view/21817
SP -
AB - 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}^n -> {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}^n -> {0,1} with cnfsize(f) <= m. We show that there are constants c_1, c_2 >= 1 and epsilon > 0 , such that for all large n and all m in [ 1/epsilon n , 2^{epsilon n}], we have <br />2^{(n - c_1) n / log(m/n)} <= dnfsize(m,n) <= 2^{(n - c_2) n / log(m/n)}.<br /> In particular, when m is the polynomial n^c, we get dnfsize(n^c,n) = 2^{(n - theta) (c^{-1} n / log n)}.
ER -