Introduction to the theory of complexity. (English) Zbl 0809.68067

Bovet, Daniel Pierre; Crescenzi, Pierluigi

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)

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