Bovet, Daniel Pierre; Crescenzi, Pierluigi Introduction to the theory of complexity. (English) Zbl 0809.68067 Prentice Hall International Series in Computer Science. London: Prentice Hall. xi, 282 p. $ 49.95 /hc (1993). This book gives the fundamentals of the computation and complexity theory. First, the computing models, basic complexity measures and complexity classes are defined. Then, the fundamental concepts, methods and proof techniques of complexity theory like robustness, polynomial- time reducibility, diagonalization, NP-completeness, relativization, approximability, nondeterministic and probabilistic computations, interactive proof systems are explained. Finally, some basis informations about parallel computing models and parallel algorithms are given.This book is a valuable textbook for use on graduate and advanced undergraduate courses in theoretical computer science. It provides a basic knowledge of computational theory as well as the basic methodology for the design of effective algorithms. Reviewer: J.Hromkovič (Kiel) Cited in 28 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) 68W15 Distributed algorithms 68W10 Parallel algorithms in computer science Keywords:complexity theory; computing models; complexity measures; complexity classes; parallel computing; parallel algorithms PDF BibTeX XML Cite \textit{D. P. Bovet} and \textit{P. Crescenzi}, Introduction to the theory of complexity. London: Prentice Hall (1993; Zbl 0809.68067) OpenURL