文章基本信息

标题：A large lower bound for 1-branching programs
本地全文：下载
作者：Petr Savicky, Stanislav Zak
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Branching programs (b.p.'s) or decision diagrams are a general graph-based model of sequential computation. B.p.'s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for different kinds of restricted b.p.'s are intensively investigated. An important restriction are so called 1-b.p.'s, where each computation reads each input bit at most once. There is a series of lower bounds for 1-b.p.'s. The largest known lower bound is due to J. Simon and M. Szegedy (improving a result of L. Babai, P. Hajnal, E. Szemeredi and G. Turan) and it is 2n2000 for an explicit function of n variables. In the present paper, a lower bound of 2n−o(n) is given for another explicit function. A generalization of the construction is also presented that may in principle lead to lower bound that almost matches a general upper bound.