TR96-050 Authors: Petr Savicky, Stanislav Zak

Publication: 30th September 1996 12:23

Downloads: 2142

Keywords:

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 so called $k$-b.p.'s,

where each computation reads each input bit at most $k$ times.

Although, for more restricted syntactic $k$-b.p.'s, exponential

lower bounds are proven and there is a series of exponential

lower bounds for $1$-b.p.'s, this is not true for general

(nonsyntactic) $k$-b.p.'s, even for $k=2$. Therefore, so

called $(1,+k)$-b.p.'s are investigated.

For some explicit functions, exponential lower bounds

for $(1,+k)$-b.p.'s are known. Investigating the syntactic

$(1,+k)$-b.p.'s, Sieling has found functions $f_{n,k}$ which

are polynomially easy for syntactic $(1,+k)$-b.p.'s, but

exponentially hard for syntactic $(1,+(k-1))$-b.p.'s. In the

present paper, a similar hierarchy with respect to $k$ is

proven for general (nonsyntactic) $(1,+k)$-b.p.'s.