Meinel C. Modified Branching Programs and Their Computational Power

Springer, 1989. — 138 p.One of the fundamental issues of complexity theory is to estimate the relative efficiency of different models of computation. A general program in doing this has been to take abstract models of computation, such as Turing machines, Random Access Machines, Boolean circuits or branching programs, and examine their behavior under certain resource constraints. This leads to the definition of complexity classes which formalize certain computational powers. By examining the meaning of and the relationships between such classes, one seeks to understand the relative strengths of their underlying computational paradigms.
In recent years the concepts of Boolean circuit complexity and other circuit based nonuniform complexities have been (re-)discovered to be useful in complexity theoretic research. They are based on computational models which are purely combinatorial objects. Apart from the strong practical interest in investigations of such circuit models, nonuniform complexity classes appear to be more amenable to combinatorial analysis.
One of the most important nonuniform models of computation are branching programs which generalize the concept of decision trees. The settings of n input variables determine a flow of control through a branching program, as each node activates one of two successors depending on the value of a tested input bit. Originally invented for the analysis of switching problems, branching programs have come to be analyzed as an abstract model of computation.
In this book we examine modified branching programs and their computational power. The most natural measure for the branching program complexity of a (Boolean) function is the size of a minimal branching program which computes this function. The well-known relations between branching program size and the space complexity of nonuniform Turing machines were the starting-point of our investigations.Branching Programs and their Computational Power
Nondeterministic Branching Programs
Ω-Branching Programs and their Computational Power
p-Projection Complete Graph Accessibility Problems