TY  - BOOK
AU  - Papadimitriou,Christos H.
TI  - Computational complexity
SN  - 0201530821
PY  - 1994///
CY  - Reading, Mass.
PB  - Addison-Wesley
KW  - Computational complexity
KW  - Computing
N1  - Includes bibliographical references and indexes
N2  - This text offers a comprehensive and accessible treatment of the theory of algorithms and complexity - the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the "structural" aspects of the P=NP question, parallel computation, the polynomial hierarchy, and many others. Several sophisticated and recent results are presented in a rather simple way, while many more are developed in the form of extensive notes, problems, and hints. The book is surprisingly self-contained, in that it develops all necessary mathematical prerequisites from such diverse fields as computability, logic, number theory, combinatorics and probability
ER  -