Branching programs (b.p.s) or binary 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. The restrictions based on the number of tests of
variables during any computation (along any path in the case of
syntactic b.p.s, resp.) are very important. Various superpoly-
nomial or even exponential lower bounds are known for 1-b.p.s,
(1,+k)-b.p.s, and syntactic k-b.p.s.
In the paper we present a restriction of another type -
the so-called gentle branching programs (g-b.p.s) together with
the following results.
1. For each 1-b.p. P there is a gentle 1-b.p. P' computing the
same function such that |P'| =< 3|P|.
2. Some Boolean functions which are superpolynomially (or even
exponentially) hard for 1-b.p.s are polynomially easy for g-b.p.s.
3. The same holds for some Boolean functions which are superpoly-
nomially hard for (1,+k)-b.p.s or for syntactic k-b.p.s.
4. The functions whose sequences cause the hierarchies for
(1,+k)-b.p.s and for syntactic k-b.p.s (both with respect to k)
are polynomially easy for g-b.p.s.
5. We find a function in P which is superpolynomially hard for
g-b.p.s. The proof is based on a lower bound theorem.
Both, the lower bound theorem and the definition of genttle
branching programs are derived from a deeper consideration of the
phenomenon of branching of computations.