ECCC-Report TR96-050https://eccc.weizmann.ac.il/report/1996/050Comments and Revisions published for TR96-050en-usMon, 30 Sep 1996 12:23:26 +0200
Paper TR96-050
| A hierarchy for (1,+k)-branching programs with respect to k |
Petr Savicky,
Stanislav Zak
https://eccc.weizmann.ac.il/report/1996/050
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.
Mon, 30 Sep 1996 12:23:26 +0200https://eccc.weizmann.ac.il/report/1996/050