Miltersen, Peter Bro ; Radhakrishnan, Jaikumar ; Wegener, Ingo (2005) On converting CNF to DNF Theoretical Computer Science, 347 (1-2). pp. 325-335. ISSN 0304-3975
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1016/j.tcs.2005.07.029
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, 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 2 n−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−θ (n/logn)).
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Circuit Size; Disjunctive Normal Form; Conjunctive Normal Form; Switching Lemma |
| ID Code: | 57646 |
| Deposited On: | 29 Aug 2011 08:37 |
| Last Modified: | 29 Aug 2011 08:37 |
Repository Staff Only: item control page
