Computational Complexity

图书标准信息

• 作者 Papadimitriou, Christos H
• 出版社 Pearson
• 出版时间 1993-11
• ISBN 9780201530827
• 定价 4836.02元
• 装帧 其他
• 页数 500页

【内容简介】

This new 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 field as computability, logic, number theory, combinatorics, and probability.FeaturesULLIFirst unified introduction to computational complexity./LILIIntegrates computation, applications, and logic throughout./LILIProvides an accessible introduction to logic, including Boolean logic, first-order logic, and second-order logic./LILIIncludes extensive exercises including historical notes, references, and challeging problems./LI/UL
  0201530821B04062001