Read-Once Branching Programs for Tree Evaluation Problems

Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman, and Santhanam introduced the Tree Evaluation Problem (TEP). For fixed integers h and k > 0, FTh(k) is given as a complete, rooted binary tree of height h, in which each root node is associated with a function from lkr2 to lkr, and each leaf node with a number in lkr. The value of an internal node v is defined naturally; that is, 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 FTh(k) needs at least kr(h) states for any unbounded function r, then this problem is not in L, thus achieving our goal. The mentioned 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 Ω(kh) states. This article 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.