bounds for width two branching programs
Branching programs for the computation of Boolean functions were first studied in the Master's thesis of Masek. 7 In a rather straightforward manner they generalize the concept of a decision tree to a decision graph. Let P be a branching program with edges labelled by the Boolean variables, x 1 ,...,x n and their complements. Given an input a&equil;(a 1 ,...,a n ) &egr; {0,1} n , program P computes a function value f p (a) in the following way. The nodes of P play the role of states or configurations. In particular, sinks play the role of final states or stopping configurations. The length of program P is the length of the longest path in P. Following Cobham, 2 capacity of the program is defined to be the logarithm to the base 2 of the number of nodes in P. Length and capacity are lower bounds on time and space requirements for any reasonable model of sequential computation. Clearly, any n-variable Boolean function can be computed by a branching program of length n if the capacity is not constrained. Since space lower bounds in excess of log n remain a fundamental challenge, we consider restricted branching programs in the hope of gaining insight into this problem and the closely related problem of time-space trade-offs.
program computation boolean function general concept decision tree graph variability input play role configurability capacities log lower bound timing space requirements model challenge