Papadimitriou, Christos H. <br/><br/>
Computational complexity / 
Christos H. Papadimitriou. 
 - Reading, Mass. :  Addison-Wesley,  c1994. 
 - xv, 523 p. :  ill. ;  25 cm. 
<br/><br/>Includes bibliographical references and indexes. 
<br/><br/> 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. 
<br/><br/><label>ISBN: </label>0201530821 
<br/><br/><label>Subjects--Topical Terms: </label><br/>Computational complexity<br/>Computing