Modified Branching Programs and Their Computational Power

Branching Programs are, besides Boolean circuits, the most important nonuniform model of computation. 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.