文章基本信息
- 标题：On Uncertainty versus Size in Branching Programs
- 本地全文：下载
- 作者：Stasys Jukna, Stanislav Zak
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2001
- 卷号：2001
- 出版社：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. The argument is based on Kraft-McMillan type inequalities for the average amount of uncertainty about (or entropy of) a given input during the various stages of computation. The uncertainty is measured by the average depth of so-caled `splitting trees' for sets of inputs reaching particular nodes of the program.
We first demonstrate the approach for read-once branching programs. Then we introduce a strictly larger class of so-called `balanced' branching programs and, using the suggested approach, prove that some explicit Boolean functions cannot be computed by balanced programs of polynomial size. These lower bounds are new since some explicit functions, which are known to be hard for most previously considered restricted classes of branching programs, can be easily computed by balanced branching programs of polynomial size.
This is a substantially simplified and conceptually different version of ECCC TR98-030.
- 关键词：branching program , decision trees , Kraft inequality , lower bounds
