zbMATH — the first resource for mathematics

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)

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