On converting CNF to DNF

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