期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let f be a Boolean function. Let N ( f ) = \dnf ( f ) + \dnf ( f ) be the sum of the minimum number of monomials in a disjunctive normal form for f and f . Let p ( f ) be the minimum size of a partition of the Boolean cube into disjoint subcubes such that f is constant on each of the subcubes. Let \dt ( f ) be the minimum size (number of leaves) of a decision tree for f . Clearly, \dt ( f ) p ( f ) N ( f ) . It is known that \dt ( f ) can be at most quasipolynomially larger than N ( f ) and a quasipolynomial separation between p ( f ) and N ( f ) for a sequence of functions f is known. We present a quasipolynomial separation between \dt ( f ) and p ( f ) for another sequence of functions f .
关键词：conjunctive normal form. , decision trees , disjunctive normal form , unambiquous nondeterminism
f ) be the sum of the minimum number of monomials in a disjunctive normal form for f and 
