文章基本信息

标题：Read-Once Branching Programs for Tree Evaluation Problems
本地全文：下载
作者：Kazuo Iwama ; Atsuki Nagao
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：409-420
DOI：10.4230/LIPIcs.STACS.2014.409
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman and Santhanam introduced the tree evaluation problem (TEP). For fixed h, k>0, FT_h(k) is given as a complete, rooted binary tree of height h, in which each internal node is associated with a function from [k]^2 to [k], and each leaf node with a number in [k]. The value of an internal node v is defined naturally, i.e., if it has a function f and the values of its two child nodes are a and b, then the value of v is f(a,b). Our task is to compute the value of the root node by sequentially executing this function evaluation in a bottom-up fashion. The problem is obviously in P and if we could prove that any branching program solving FT_h(k) needs at least k^(r(h)) states for any unbounded function r, then this problem is not in L, thus achieving our goal. The above authors introduced a restriction called thrifty against the structure of BP's (i,e., against the algorithm for solving the problem) and proved that any thrifty BP needs Omega(k^h) states. This paper proves a similar lower bound for read-once branching programs, which allows us to get rid of the restriction on the order of nodes read by the BP that is the nature of the thrifty restriction.
关键词：Lower bounds; Branching Programs; Read-Once Branching Programs; Space Complexity; Combinatorics