文章基本信息

标题：A hierarchy for (1,+k)-branching programs with respect to k
本地全文：下载
作者：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. The 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 k-b.p.'s, where each computation reads each input bit at most k times. Although, for more restricted syntactic k-b.p.'s, exponential lower bounds are proven and there is a series of exponential lower bounds for 1-b.p.'s, this is not true for general (nonsyntactic) k-b.p.'s, even for k=2. Therefore, so called (1+k) -b.p.'s are investigated. For some explicit functions, exponential lower bounds for (1+k) -b.p.'s are known. Investigating the syntactic (1+k) -b.p.'s, Sieling has found functions fnk which are polynomially easy for syntactic (1+k) -b.p.'s, but exponentially hard for syntactic (1+(k−1)) -b.p.'s. In the present paper, a similar hierarchy with respect to k is proven for general (nonsyntactic) (1+k) -b.p.'s.