Branching Programs are, besides Boolean circuits, the most important
nonuniform model of computation. This volume gives a survey of the
latest research in this field. It presents a branching program-based
approach to complexity theory. Starting with a definition of branching
programs and a review of the former research, nondeterministic branching
programs are introduced and investigated, thus allowing the description
of some fundamental complexity classes. The book then concentrates on
the new concept of Omega-branching programs. Apart from the usual binary
tests they contain features for evaluating certain elementary Boolean
functions and are suited for characterizing space-bounded complexity
classes. By means of these characterizations the author demonstrates the
separation of some restricted complexity classes. In the appendix a
number of extremely restricted graph-accessibility problems are given,
which are, due to the branching program descriptions in chapters 1-3,
p-projection complete in the classes under consideration.