A read-once lower bound and a (1,+k)-hierarchy for branching programs

AbstractBranching programs (b.p.'s) or decision diagrams are a general graph-based model of sequential computation. The 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 k-b.p.'s, where each computation reads each input variable at most k times.Although exponential lower bounds have been proven for syntactic k-b.p.'s, this is not true for general (nonsyntactic) k-b.p.'s, even for k=2. Therefore, the so-called (1,+k)-b.p.'s are investigated.For some explicit functions, exponential lower bounds for (1,+k)-b.p.'s are known. We prove that the hierarchy of (1,+k)-b.p.'s w.r.t. k is strict. More exactly, we present (multipointer) functions fn,k which are polynomially easy for (1,+k)-b.p.'s, but exponentially hard for (1,+(k−1))-b.p.'s for k⩽12n1/6/log1/3n. This is a generalization of a similar result of Sieling [20] for syntactic (1,+k)-branching programs.As a by-product, we prove a lower bound of 2n−3n for an explicit (pointer) function in P