Christoph Meinel, Humboldt-Universität Berlin
Modified Branching Programs and Their Computational Power
Contents
Preliminaries
1. Branching Programs and their Computational Power
* Introduction
* 1.1. Branching Programs
* 1.2. Bounded width branching programs
* 1.3. Read-once-only branching programs
2. Nondeterministic Branching Programs
* Introduction
* 2.1. Nondeterministic branching programs and their classification
* 2.2. The computational power of nondeterministic branching programs of polynominal size
* 2.2.1. 1-time-only-nondeterministic branching programs of polynomial size
* 2.2.2. Nondeterministic branching programs of polynomial size
* 2.3. Nondeterministic bounded width branching programs of polynomial size
* 2.3.1. 1-time-only-nondeterministic bounded width branching programs of polynomial size
* 2.3.2 Nondeterministic bounded width branching programs of polynomial size
3. Omega-Branching Programs and their computational power
* Introduction
* 3.1. Omega-branching programs and their classification
* 3.1.1. Omega-branching programs
* 3.1.2. Classification
* 3.2. Omega-branching programs of polynomial size
* 3.2.1. Complexity classes related to polynomial size Omega-branching programs
* 3.2.2. Relationship between these complexity classes
* 3.3. Bounded with Omega-branching programs of polynomial size
* 3.4. Omega-branching programs of quasipolynomial size
* 3.4.1. Complexity classes related to Omega-branching programs of quasipolynomial size
* 3.4.2. Relationship between these classes
* 3.5. Read-once-only Omega-branching programs of polynomial size
* 3.5.1. Complexity classes related to polynomial size read-once-only Omega-branching programs
* 3.5.2. Classification of the read-once-only complexity classes
* 3.5.3 Some lower and upper bounds
* 3.5.4. Separating the complexity classes related to polynomial size read-once-only Omega-branching programs
Appendix
p-Projection Complete Graph Accessibility Problems
References
Index
INTRODUCTION
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 bases 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. Results obtained by Furst, Saxe and Sipser [FSS84], Razborov [Ra85], [Ra86], Andreev [An85], Yao [Ya85], Hastad [Ha86], Barrington [Ba86] and many others have advanced our knowledge of nonuniform complexity classes as well as of complexity classes in general.
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 thesis 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 [Co66], [Bu82], [PZ83] were the starting-point of our investigations.
First, we introduce and examine nondeterministic branching programs. It is found that the computational power of nondeterministic branching programs is mainly determined by their ability to record nondeterministic choices. While the size of 1-time-only-nondeterministic branching programs is related to nondeterministic (nonuniform) Turing machine space, the size of unrestricted nondeterministic branching programs is related to nondeterministic (nonuniform) Turing machine time [Me86,2]. Furthermore, nondeterministic and 1-time-only-nondeterministic branching programs respond differently to bounding their width. While nondeterministic bounded width branching programs turn out to be as powerful as nondeterministic branching programs without any width constraints, 1-time-only-nondeterminism does not even increase the computational power of (ordinary) bounded width branching programs.
We then generalize the concept of 1-time-only-nondeterministic branching programs by introducing Omega-branching programs. Omega-branching programs are branching programs some of whose nodes are capable of evaluating Boolean functions from a set Omega \subset B_2 of 2-argument Boolean functions. We prove that complexity classes defined by Omega-branching programs fit closely into the framework of already studied classes defined by Turing machines or Boolean circuits. We completely classify Omega-branching programs into ordinary, disjunctive, conjunctive, parity and alternating branching programs, and relate the size of these branching programs to the space of nonuniform deterministic, nondeterministic, co-nondeterministic, "parity" and alternating Turing machines, respectively. Hence, four of the five types of Omega-branching programs correspond to well-known types of Turing machines whereas the fifth type has not been identified up to now in the context of space-bounded Turing machines.
The study of the influence of certain resource constraints on Omega-branching programs yields interesting results also for the corresponding Turing machine classes. For example, polynomial size parity, ordinary, disjunctive, conjunctive and alternating branching programs define the newly discovered class parity L as well as such fundamental complexity classes like L, NL = co-NL and P, respectively, which are strongly expected to be different. Unlike polynomial size bounded width Omega-branching programs, for all Omega \subset B_2 they define the same class coinciding with NC^1. While all the classes defined by polynomial size-bounded and unbounded width Omega-branching programs are conjectured to be different most of the corresponding complexity classes defined by quasipolynomial size Omega-branching programs coincide for sure.
However, one of the most interesting and important tasks in complexity theory is to separate complexity classes such as L, NL (= co-NL) or P (or fo prove their coincidence). Since we have described these complexity classes by means of polynomial size ordinary, disjunctive, conjunctive and alternating branching programs, respectively, super polynomial lower bounds for such branching programs would essentially contribute to a separation of these classes. In cooperation with M. Krause and S. Waack we succeeded in separating ordinary, disjunctive, conjunctive and alternating read-once-only branching programs [KMW88] this improving corresponding results for ordinary read-once-only branching programs [We84], [A&86], [KW87]. This is especially interesting since these read-once-only Omega-branching program complexity classes correspond to the nonuniform logarithmic space bounded eraser Turing machine classes L_e, NL_e, co-NL_e and P_e. We obtain
L_e \subsetneq NL_e \subsetneq P_e = P,
and L_e \subsetneq co-NL_e \subsetneq P_e,
and co-NL_e is uncomparable to NL_e.
Since up to now only L_e was separated we have carried out by L_e \subsetneq NL_e, L_e \subsetneq co-NL_e and NL_e \subsetneq P_e, co-NL_e \subsetneq P_e further steps in separating larger and larger complexity classes.
Finally, we are able to use the given branching program characterizations of various nonuniform complexity also for achieving p-projection completeness results. In particular, we have proved the p-projection completeness of a number of GRAPH-ACCESSIBILITY-PROBLEMS and certain restricted NETWORK-FLOW-PROBLEMS strengthening, unifying, and generalizing classical results of [Sa70], [CSV84]. Beside giving new insights into the capabilities of computations within certain complexity bounds varying the complexity of one and the same problem makes the "differences" of the corresponding complexity classes more evident.
This thesis contains the results of [Me86,1-2], [Me87,1-4], [Me88] and [KMW88], along with some additional material not yet published. It is organized as follows:
In the first chapter we introduce the concept of branching programs (Section 1.1) and review some previous results. In particular we are interested in the effect upon branching programs of tight constraints on width or on the input access. In Section 1.2 we review some of the previous results concerning bounded width branching programs. In particular we cite Barrington´s result, which relates bounded width branching programs and certain depth restricted Boolean fa-in 2 circuits [Ba86]. The second important resource constraint for branching programs is that of restricting the number of accesses to the input variables on each path of computation. The most investigated case is that of read-once-only branching programs where each variable may be tested only once on each path. For read-once-only branching programs a number of even exponential lower bounds were obtained. A short review of these results is given in Section 1.3.
In the second chapter we examine nondeterministic branching programs which have been introduced in [Me86,1]. Apart from giving the possibility to describe higher (nonuniform) complexity classes by means of certain branching programs the concept of nondeterminism overcomes some restrictioncs in the branching program model. Section 2.1 introduces nondeterministic branching programs and classifies them according to their ability to record nondeterministic choices. In Section 2.2 we compare the computational power of nondeterministic and 1-time-only-nondeterministic branching programs of polynomial size. In the final Section 2.3 the influence of bounding the width on the computational power of nondeterministic branching programs is studied.
Chapter 3 deals with Omega-branching programs, Omega \subset B_2, and their computational power. After classifying in Section 3.1 Omega-branching programs into the five types of ordinary, disjunctive {or}-branching programs, conjunctive {and}-branching programs, parity {parity}-branching programs and alternating {or,and}-branching programs under different resource constraints. At first, in Section 3.2, we let the size of such Omega-branching programs be polynomial bounded. In Section 3.3 we study polynomial size Omega-branching programs of bounded width. Section 3.4 examines quasipolynomial size Omega-branching programs, Omega \subset B_2. In order to separate larger complexity classes we investigate in the final Section 3.5 read-once-only Omega-branching programs, Omega \subset B_2. Indeed this approach proved to be quite successful since it is possible to separate the complexity classes which are related to polynomial size read-once-only Omega-branching programs, Omega \in {\emptyset, {or}, {and}, {or,and}}.
In the appendix we consider some very restricted GRAPH-ACCESSIBILITY-PROBLEMS and prove their p-projection completeness in the complexity classes described in Chapters 1 to 3 by means of certain Omega-branching programs. For that purpose we give a number of Omega-branching programs which solve these GRAPH-ACCESSIBILITY-PROBLEMS.
At last technical remark should be made. Within each chapter all propositions, lemmas and corollaries are numbered continuously. In order to keep references within the text as short as possible the number of theorems is the same as that of the paragraph where the proof is given.
