Parallel Complexity Theory

Author(s): Ian Parberry, Department of Computer Sciences, University of North Texas

Terms and Conditions :


Book excerpts:

Parallel complexity theory, the study of resource-bounded parallel computation, is surely one of the fastest-growing areas of theoretical Computer Science (ed: this book was written in 1987). 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 majority) 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, Hopcroft and Ullman, Garey and Johnson, and Aho, Hopcroft and Ullman.

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.

View/Download Parallel Complexity Theory

All free books by Ian Parberry are now referenced on this site.