ECCC-Report TR03-017https://eccc.weizmann.ac.il/report/2003/017Comments and Revisions published for TR03-017en-usThu, 27 Mar 2003 13:30:15 +0200
Paper TR03-017
| On Converting CNF to DNF |
Peter Bro Miltersen,
Jaikumar Radhakrishnan,
Ingo Wegener
https://eccc.weizmann.ac.il/report/2003/017The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions 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)).
Thu, 27 Mar 2003 13:30:15 +0200https://eccc.weizmann.ac.il/report/2003/017