期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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)).
