A large lower bound for 1-branching programs
Petr Savický, Stanislav Žák · Digital Repository (National Repository of Grey Literature) · 1996
Branching programs (b. p.'s) or decision diagrams are a general graph-based model of sequential computation. B.p.'s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for different kinds of restricted b. p.'s are intensively investigated. An important restriction are the so called 1--b. p.'s, where each computation reads each input bit at most once. There is a series of lower bounds for 1--b. p.'s. The largest known lower bound was 2 n=2000 for a function of n variables, see [14]. In the present paper, a lower bound of 2 n\\Gamma3 p n is given for an explicit function. A generalization of the construction is also presented that may in principle lead to a lower bound that almost matches a general upper bound. 1 Introduction A branching program (b. p.) is a computation model for representing Boolean functions. The input of a branching program is a vector consisting of n input bits. The branching program itself is a directed acyclic graph with one source. The out-d...