A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs (Q1575258): Difference between revisions

Branching 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 \(f_{n,k}\) which are polynomially easy for \((1,+k)\)-b.p.'s, but exponentially hard for \((1,+(k-1))\)-b.p.'s for \(k\leqslant \frac 12n^{1/6}/\log^{1/3}n\). This is a generalization of a similar result of \textit{D. Sieling} [J. Comput. Syst. Sci. 53, No.~1, 79-87, Art. No.~0050 (1996; Zbl 0859.68027)] for syntactic \((1,+k)\)-branching programs. As a by-product, we prove a lower bound of \(2^{n-3\sqrt n}\) for an explicit (pointer) function in P.