文章基本信息

标题：On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs
本地全文：下载
作者：S. Jukna ; A. Razborov ; Petr Savicky 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：It is known that if a Boolean function f in n variables has a DNF and a CNF of size at most N then f also has a (deterministic) decision tree of size exp(O(lognlog2N). We show that this simulation {\em cannot} be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp((log2N)) where N is the total number of monomials in minimal DNFs for f and \neg f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen-Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Whereas other examples have the additional property that f is in AC^0.