Almost the same types of restricted branching programs (or
binary decision diagrams BDDs) are considered in complexity
theory and in applications like hardware verification. These
models are read-once branching programs (free BDDs) and certain
types of oblivious branching programs (ordered and indexed BDDs
with k layers). The complexity of the satisfiability problem
for these restricted branching programs is investigated and
tight hierarchy results are proved for the classes of functions
representable by k layers of ordered or indexed BDDs of
polynomial size.