文章基本信息

标题：On Branching Programs With Bounded Uncertainty
本地全文：下载
作者：Stasys Jukna, Stanislav Zak
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We propose an information-theoretic approach to proving lower bounds on the size of branching programs (b.p.). The argument is based on Kraft-McMillan type inequalities for the average amount of uncertainty about (or entropy of) a given input during various stages of the computation. We first demonstrate the approach for read-once b.p. Then we introduce a strictly larger class of so-called "gentle" b.p. and, using the suggested approach, prove that some explicit Boolean functions, including the Clique function and a particular Pointer function (which belongs to AC^0), cannot be computed by gentle program of polynomial size. These lower bounds are new since explicit functions, which are known to be hard for all previously considered reading-restricted classes of b.p. (such as (1,+s)-b.p. or syntactic read-k-times b.p.) can be easily computed by gentle b.p. of polynomial size.
关键词：branching programs, entropy, lower bounds, stable functions