计算复杂性的现代方法

出版时间：2012-1  出版社：世界图书出版公司  作者：阿罗拉  页数：579  
Tag标签：无  

内容概要

　　本书是一部将所有有关复杂度知识理论集于一体的教程。将最新进展和经典结果结合起来，是一部很难得的研究生入门级教程。既是相关科研人员的一部很好的参考书，也是自学人员很难得的一本很好自学教程。本书一开始引入该领域的最基本知识，然后逐步深入，介绍更多深层次的结果，每章末都附有练习。对复杂度感兴趣的人士，物理学家，数学家以及科研人员这本书都是相当受益。

书籍目录

About this bOok
Acknowledgments
Introduction
0 Notational conventions
PARTONE: BASIC COMPLEXITY CLASSES
　1 The computational model--and why it doesn't matter
　2 NP and NP completeness
　3 Diagonalization
　4 Space complexity
　5 The polynomial hierarchy and alternations
　6 Boolean circuits
　7 Randomized computation
　8 Interactive proofs
　9 Cryptography
　10 Quantum computation
　11 PCP theorem and hardness of approximation: An
introduction
PART TWO: LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS
　12 Decision trees
　13 Communication complexity
　14 Circuit lower bounds: Complexity theory's Waterloo
　15 Proof complexity
　16 Algebraic computation models
PART THREE: ADVANCED TOPICS
　17 Complexity of counting
　18 Average case complexity: Levin's theory
　19 Hardness amplification and error-correcting codes
　20 Derandomization
　21 Pseudorandom constructions: Expanders and extractors
　22 Proofs of PCP theorems and the Fourier transform
technique
　23 Why are circuit lower bounds so difficult?
Appendix: Mathematical background
Hints and selected exercises
Main theorems and definitions
Bibliography
Index
Complexity class index

章节摘录

版权页：   插图：   Physicists， mathematicians， and other scientists． This group has become increasinglyinterested in computational complexity heory， especially because of high—profile results such as Shor's algorithm and the recent deterministic test for primality． This intellectually sophisticated group will be able to quickly read through Part Ⅰ． Progressing on to Parts Ⅱ and Ⅲ， they can read individual chapters and find almost everything they needto understand current research． Computer scientists who do not work in complexity theory per se． They may use the book for self—study， reference， or to teach an undergraduate or graduate course in theory of computation or complexity theory．Anyone——professors or students——who does research in complexity theory or plans to do so． The coverage of recent results and advanced topics is detailed enough to prepare readers for research in complexity and related areas． Undergraduate theory of computation． Many computer science （CS） departments offer an undergraduate Theory of Computation course， using， say， Sipser's book （Sip96）． Our text could be used to supplement Sipser's book with coverage of some more modern topics， such as probabilistic algorithms， cryptography， and quantum computing． Undergraduate students may find these more exciting than traditional topics， such as automata theory and the finer distinctions of computability theory． The prerequisite mathematical background would be some comfort with mathematical proofs and discrete mathematics， as covered in the typical "discrete math" or "math for CS" courses currently offered in many CS departments． Introduction to computational complexity for advanced undergrads or beginning grads．The book can be used as a text for an introductory complexity course aimed at advanced undergraduate or graduate students in computer science （replacing books such as Papadimitriou's 1994 text （Pap94） that do not contain many recent results）． Such a course would probably include many topics from Part Ⅰ and then a sprinkling from PartsⅡ and Ⅲ and assume some background in algorithms and/or the theory of computation．Graduate complexity course． The book can serve as a text for a graduate complexitycourse that prepares graduate students for research in complexity theory or related areas like algorithms and machine learning． Such a course can use Part Ⅰ to review basic material and then move on to the advanced topics of Parts Ⅱ and Ⅲ． The book contains far more material than can be taught in one term， and we provide on our Web site several alternative outlines for such a course．

用户评论 (总计7条)

•   ****://***.cs.princeton.edu/~arora/ 这是Arora的简介这本书研究的 是计算机科学中研究计算复杂性，怎么会被分到物理学经典教材里面去呢？
•   好全的不本书呀 希望有时间好好拜读一下
•   还行 买的太着急了~~买重了~~浪费了哈~~
•   这本书真是好啊，建议大家认真学习
•   书很好，崭新、印刷清晰，由于之前一直看的是复印本，总算可以舒服地读了。很划算
•   是正版书，需要的同学可以放心购买。该书算是学习计算复杂性的很好的书籍了吧，讲的很全面。建议搞懂了图灵机的概念再来看这本书。
•   书的内容不错，不过要看懂估计还得费点劲。