計(jì)算復(fù)雜性的現(xiàn)代方法

內(nèi)容概要

　　本書是一部將所有有關(guān)復(fù)雜度知識(shí)理論集于一體的教程。將最新進(jìn)展和經(jīng)典結(jié)果結(jié)合起來(lái)，是一部很難得的研究生入門級(jí)教程。既是相關(guān)科研人員的一部很好的參考書，也是自學(xué)人員很難得的一本很好自學(xué)教程。本書一開始引入該領(lǐng)域的最基本知識(shí)，然后逐步深入，介紹更多深層次的結(jié)果，每章末都附有練習(xí)。對(duì)復(fù)雜度感興趣的人士，物理學(xué)家，數(shù)學(xué)家以及科研人員這本書都是相當(dāng)受益。

書籍目錄

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

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   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．

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    計(jì)算復(fù)雜性的現(xiàn)代方法 PDF格式下載

---