Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-050 | 23rd September 1996 00:00

A hierarchy for (1,+k)-branching programs with respect to k


Authors: Petr Savicky, Stanislav Zak
Publication: 30th September 1996 12:23
Downloads: 1082


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.

ISSN 1433-8092 | Imprint