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.


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