计算复杂性的现代方法

章节摘录

版权页：   插图：   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．

书籍目录

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

作者简介

《计算复杂性的现代方法》内容简介：This book aims to describe such recent achievements of complexity theory in the context of more classical results． It is intended to serve both as a textbook and as a reference for self—study． This means it must simultaneously cater to many audi-

ences， and it is carefully designed with that goal in mind． We assume essentiallyno computational background and very minimal mathematical background， which we review in Appendix A．

图书封面

---

 计算复杂性的现代方法下载

---