Name
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}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 ≤ 2n-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 c1, c2 ≥ 1 and ε 0, such that for all large n and all m ∈ [ 1/ε n, 2εn], we have 2n-c1(n/log(m/n)) ≤ dnfsize(m, n) ≤ 2n-c2(n/log(m/n)). In particular, when m is the polynomial nc, we get dnfsize(nc, n) = 2n-θ(c-1(n/log n)). |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.tcs.2005.07.029 | Theoretical Computer Science |
Keywords | Field | DocType |
boolean function,conjunctive normal form,disjunctive normal form | Boolean function,Binary logarithm,Discrete mathematics,Combinatorics,Polynomial,Function representation,Mathematics | Journal |
Volume | Issue | ISSN |
347 | 1-2 | 0304-3975 |
Citations | PageRank | References |
14 | 0.86 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Bro Miltersen | 1 | 1146 | 94.49 |
| Jaikumar Radhakrishnan | 2 | 1123 | 96.04 |
| Ingo Wegener | 3 | 2663 | 210.34 |
| MiltersenPeter Bro | 4 | 45 | 2.30 |