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.