an excellent reference manual. ... All the chapters are well written, and the extensive bibliography is useful. The authors have been extremely thorough and careful. ... the theory of P-completeness gives us important insights into the nature of the limits of parallel computation, and Greenlaw, Hoover, and Ruzzo have written an excellent reference work. I recommend it highly.

• PART I: Background and Theory 1: Introduction 2: Parallel Models and Complexity Classes 3: Two Basic P-Complete Problems 4: Evidence that NC Does Not Equal P 5: The Circuit Value Problem 6: Parallel Versions of Sequential Paradigms 7: Boolean Circuits PART II: P-Complete and Open Problems 8: List of P-Complete Problems 9: Open Problems