Greenlaw, Raymond; Hoover, H. James; Ruzzo, Walter L. Limits to parallel computation. P-completeness theory. (English) Zbl 0829.68068 Oxford: Oxford Univ. Press. xiii, 311 p. (1995). The book begins with a short introduction to the existence of inherently sequential problems and some historical remarks. The following part I is devoted to the theory of P-completeness. The two main models discussed are the parallel random access machine (PRAM) and the uniform Boolean circuit family. The basic notions of reducibility and completeness and two prototypes for P-complete problems follow (Generic Machine Simulation and the Circuit Value Problem CVP). P-complete variants of CVP are investigated later. Relations between greedy algorithms and P- completeness are discussed. Other topics discussed are the notions of strong and strict P-completeness and approximations to P-complete problems. Part II contains lists of P-complete problems and of some open questions. Almost 400 references conclude this very interesting and useful work. Reviewer: H.-D.Hecker (Jena) Cited in 125 Documents MSC: 68W15 Distributed algorithms 68Q25 Analysis of algorithms and problem complexity 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) 68-02 Research exposition (monographs, survey articles) pertaining to computer science Keywords:\(P\)-complete problems; generic machine simulation; circuit value problem; parallel random access machine; uniform Boolean circuit family PDFBibTeX XMLCite \textit{R. Greenlaw} et al., Limits to parallel computation. P-completeness theory. Oxford: Oxford Univ. Press (1995; Zbl 0829.68068)