Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-017 | 27th March 2003 00:00

On Converting CNF to DNF

RSS-Feed




TR03-017
Authors: Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
Publication: 27th March 2003 13:30
Downloads: 3601
Keywords: 


Abstract:

The 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)).



ISSN 1433-8092 | Imprint