Parallel complexity theory, the study of resource-bounded parallel computation, is surely one of the fastest-growing areas of theoretical Computer Science. In the light of this, it would be foolish to attempt an encyclopedic coverage of the field. However, it is the belief of the author that its foundations are becoming increasingly clear and well-defined. This Monograph is an attempt to present these foundations in a unified and coherent manner.
The material contained herein is aimed at advanced Graduate students or researchers in theoretical Computer Science who wish to gain an insight into parallel complexity theory. It is assumed that the reader has (in addition to a certain level of mathematical maturity) a general knowledge of Computer Science, and familiarity with automata theory, formal languages, complexity theory and analysis of algorithms. The interested reader may wish to augment his or her knowledge with books by Goldschlager and Lister [47], Hopcroft and Ullman[57], Garey and Johnson [39] and Aho, Hopcroft and Ullman [3].
This Monograph contains some of results that the author feels are fundamental, important, or exceptionally beautiful. The reader is free to make his or her own judgements. Lack of space and the current dynamic nature of the field prevent coverage of much recent material. In particular, results that are probabilistic in nature (both probabilistic proofs and results that concern probabilistic computations) have in general been avoided. This Monograph could not hope to do justice to so large and complicated a topic in the limited space available. There are sufficient results in probabilistic complexity theory to warrant a book devoted entirely to that subject.
The main part of this Monograph consists of twelve chapters. Chapter 1, the Introduction, sets the scene for the remainder of the work by elucidating our aims and motivation. Chapter 2 examines some early work in the field including sorting networks, permutation networks and the parallel prefix problem. Chapters 3 and 4 develop a parallel machine model that we will use throughout the remainder of the Monograph. Chapter 5 examines the parallel computation thesis, which is an attempt to characterize time-bounded parallel computation in terms of space-bounded sequential computation. In Chapter 6 we explore the computational power of our machine model by providing upper and lower-bounds for some problems of interest. Chapter 7 contains some elementary results concerning a restricted variant of our machine model. Chapter 8 deals with the asymptotically optimal sorting network of Ajtai, Komlos and Szemeredi [5,6]. The results of Chapters 7 and 8 will be used in Chapter 9 to provide a restricted network which is universal for the general model with a modest increase inresources. Chapter 9 also considers the extended parallel computation thesis, an attempt to characterize time and hardware-bounded parallel computation. Chapter 10 is devoted to a more detailed discussion of universal parallel machines, whilst Chapter 11 covers unbounded fan-in parallelism and provides anew parallel computation thesis which operates in that framework. Finally, Chapter 12 is the Conclusion, which attempts to summarize and put into perspectivethe results of the previous ten chapters.