计算复杂性(英文版)(图灵原版计算机科学系列)(Computational Complexity:A Conceptual Perspective)

基本信息·出版社：人民邮电出版社

·页码：606 页

·出版日期：2010年04月

·ISBN：9787115224002

·条形码：9787115224002

·版本：第1版

·装帧：平装

·开本：16

·正文语种：英语

·丛书名：图灵原版计算机科学系列

·外文书名：Computational Complexity:A Conceptual Perspective

产品信息有问题吗？请帮我们更新产品信息。

内容简介本书是理论计算机科学领域的名著。书中对计算任务的固有复杂性研究进行了一般性介绍，涉及了复杂性理论的很多子领域，涵盖了NP完整性、空间复杂性、随机性和计数、伪随机数生成器等内容，还在附录里面给出了现代密码学基础等内容。 本书内容严谨，可读性强，适合作为高年级本科生、研究生的教材，对涉及计算复杂性的专业人员也是理想的技术参考书。

目录

Contents 1Introduction and Preliminaries1 1.1Introduction1 1.1.1A Brief Overview of Complexity Theory2 1.1.2Characteristics of Complexity Theory6 1.1.3Contents of This Book8 1.1.4Approach and Style of This Book12 1.1.5Standard Notations and Other Conventions16 1.2Computational Tasks and Models17 1.2.1Representation18 1.2.2Computational Tasks18 1.2.3Uniform Models (Algorithms)20 1.2.4Non-uniform Models (Circuits and Advice)36 1.2.5Complexity Classes42 Chapter Notes43 2P, NP, and NP-Completeness44 2.1The P Versus NP Question46 2.1.1The Search Version: Finding Versus Checking47 2.1.2The Decision Version: Proving Versus Verifying50 2.1.3Equivalence of the Two Formulations54 2.1.4Two Technical Comments Regarding NP55 2.1.5The Traditional Definition of NP55 2.1.6In Support of P Different from NP57 2.1.7Philosophical Meditations58 2.2Polynomial-Time Reductions58 2.2.1The General Notion of a Reduction59 2.2.2Reducing Optimization Problems to Search Problems61 2.2.3Self-Reducibility of Search Problems63 2.2.4Digest and General Perspective67 2.3NP-Completeness67 2.3.1Definitions68 2.3.2The Existence of NP-Complete Problems69 2.3.3Some Natural NP-Complete Problems71 2.3.4NP Sets That Are Neither in P nor NP-Complete81 2.3.5Reflections on Complete Problems85 2.4Three Relatively Advanced Topics87 2.4.1Promise Problems87 2.4.2Optimal Search Algorithms for NP92 2.4.3The Class coNP and Its Intersection with NP94 Chapter Notes97 Exercises99 3Variations on P and NP108 3.1Non-uniform Polynomial Time (P/poly)108 3.1.1Boolean Circuits109 3.1.2Machines That Take Advice111 3.2The Polynomial-Time Hierarchy (PH)113 3.2.1Alternation of Quantifiers114 3.2.2Non-deterministic Oracle Machines 117 3.2.3The P/poly Versus NP Question and PH119 Chapter Notes121 Exercises122 4More Resources, More Power127 4.1Non-uniform Complexity Hierarchies128 4.2Time Hierarchies and Gaps129 4.2.1Time Hierarchies129 4.2.2Time Gaps and Speedup136 4.3Space Hierarchies and Gaps139 Chapter Notes139 Exercises140 5Space Complexity143 5.1General Preliminaries and Issues144 5.1.1Important Conventions144 5.1.2On the Minimal Amount of Useful Computation Space145 5.1.3Time Versus Space146 5.1.4Circuit Evaluation153 5.2Logarithmic Space153 5.2.1The Class L154 5.2.2Log-Space Reductions154 5.2.3Log-Space Uniformity and Stronger Notions155 5.2.4Undirected Connectivity155 5.3Non-deterministic Space Complexity162 5.3.1Two Models162 5.3.2NL and Directed Connectivity164 5.3.3A Retrospective Discussion171 5.4PSPACE and Games172 Chapter Notes175 Exercises175 6Randomness and Counting184 6.1Probabilistic Polynomial Time185 6.1.1Basic Modeling Issues186 6.1.2Two-Sided Error: The Complexity Class BPP189 6.1.3One-Sided Error: The Complexity Classes RP and coRP193 6.1.4Zero-Sided Error: The Complexity Class ZPP199 6.1.5Randomized Log-Space199 6.2Counting202 6.2.1Exact Counting202 6.2.2Approximate Counting211 6.2.3Searching for Unique Solutions217 6.2.4Uniform Generation of Solutions220 Chapter Notes227 Exercises230 7The Bright Side of Hardness241 7.1One-Way Functions242 7.1.1Generating Hard Instances and One-Way Functions243 7.1.2Amplification of Weak One-Way Functions245 7.1.3Hard-Core Predicates250 7.1.4Reflections on Hardness Amplification255 7.2Hard Problems in E255 7.2.1Amplification with Respect to Polynomial-Size Circuits257 7.2.2Amplification with Respect to Exponential-Size Circuits270 Chapter Notes277 Exercises278 8Pseudorandom Generators284 Introduction285 8.1The General Paradigm288 8.2General-Purpose Pseudorandom Generators290 8.2.1The Basic Definition291 8.2.2The Archetypical Application292 8.2.3Computational Indistinguishability295 8.2.4Amplifying the Stretch Function299 8.2.5Constructions301 8.2.6Non-uniformly Strong Pseudorandom Generators304 8.2.7Stronger Notions and Conceptual Reflections305 8.3Derandomization of Time-Complexity Classes307 8.3.1Defining Canonical Derandomizers308 8.3.2Constructing Canonical Derandomizers310 8.3.3Technical Variations and Conceptual Reflections313 8.4Space-Bounded Distinguishers315 8.4.1Definitional Issues316 8.4.2Two Constructions 318 8.5Special-Purpose Generators325 8.5.1Pairwise Independence Generators326 8.5.2Small-Bias Generators329 8.5.3Random Walks on Expanders332 Chapter Notes334 Exercises337 9Probabilistic Proof Systems349 9.1Interactive Proof Systems352 9.1.1Motivation and Perspective352 9.1.2Definition354 9.1.3The Power of Interactive Proofs357 9.1.4Variants and Finer Structure: An Overview363 9.1.5On Computationally Bounded Provers: An Overview366 9.2Zero-Knowledge Proof Systems368 9.2.1Definitional Issues369 9.2.2The Power of Zero-Knowledge372 9.2.3Proofs of Knowledge–A Parenthetical Subsection378 9.3Probabilistically Checkable Proof Systems380 9.3.1Definition381 9.3.2The Power of Probabilistically Checkable Proofs383 9.3.3PCP and Approximation398 9.3.4More on PCP Itself: An Overview401 Chapter Notes404 Exercises406 10Relaxing the Requirements416 10.1Approximation417 10.1.1Search or Optimization418 10.1.2Decision or Property Testing423 10.2Average-Case Complexity428 10.2.1The Basic Theory430 10.2.2Ramifications442 Chapter Notes451 Exercises453 Epilogue461 Appendix A: Glossary of Complexity Classes463 A.1Preliminaries463 A.2Algorithm-Based Classes464 A.2.1Time Complexity Classes464 A.2.2Space Complexity Classes467 A.3Circuit-Based Classes467 Appendix B: On the Quest for Lower Bounds469 B.1Preliminaries469 B.2Boolean Circuit Complexity471 B.2.1Basic Results and Questions472 B.2.2Monotone Circuits473 B.2.3Bounded-Depth Circuits473 B.2.4Formula Size474 B.3Arithmetic Circuits475 B.3.1Univariate Polynomials476 B.3.2Multivariate Polynomials476 B.4Proof Complexity478 B.4.1Logical Proof Systems480 B.4.2Algebraic Proof Systems480 B.4.3Geometric Proof Systems481 Appendix C: On the Foundations of Modern Cryptography482 C.1Introduction and Preliminaries482 C.1.1The Underlying Principles483 C.1.2The Computational Model485 C.1.3Organization and Beyond486 C.2Computational Difficulty487 C.2.1One-Way Functions487 C.2.2Hard-Core Predi cates489 C.3Pseudorandomness490 C.3.1Computational Indistinguishability 490 C.3.2Pseudorandom Generators491 C.3.3Pseudorandom Functions492 C.4Zero-Knowledge494 C.4.1The Simulation Paradigm494 C.4.2The Actual Definition494 C.4.3A General Result and a Generic Application495 C.4.4Definitional Variations and Related Notions497 C.5Encryption Schemes500 C.5.1Definitions502 C.5.2Constructions504 C.5.3Beyond Eavesdropping Security505 C.6Signatures and Message Authentication507 C.6.1Definitions508 C.6.2Constructions509 C.7General Cryptographic Protocols511 C.7.1The Definitional Approach and Some Models512 C.7.2Some Known Results517 C.7.3Construction Paradigms and Two Simple Protocols517 C.7.4Concluding Remarks522 Appendix D: Probabilistic Preliminaries and Advanced Topics inRandomization523 D.1Probabilistic Preliminaries523 D.1.1Notational Conventions523 D.1.2Three Inequalities524 D.2Hashing528 D.2.1Definitions528 D.2.2Constructions529 D.2.3The Leftover Hash Lemma529 D.3Sampling533 D.3.1Formal Setting533 D.3.2Known Results534 D.3.3Hitters535 D.4Randomness Extractors536 D.4.1Definitions and Various Perspectives537 D.4.2Constructions541 Appendix E: Explicit Constructions545 E.1Error-Correcting Codes546 E.1.1Basic Notions546 E.1.2A Few Popular Codes547 E.1.3Two Additional Computational Problems551 E.1.4A List-Decoding Bound553 E.2Expander Graphs554 E.2.1Definitions and Properties555 E.2.2Constructions561 Appendix F: Some Omitted Proofs566 F.1Proving That PH Reduces to #P566 F.2Proving That IP(f) ? AM(O(f)) ? AM(f)572 F.2.1Emulating General Interactive Proofs by AM-Games572 F.2.2Linear Speedup for AM578 Appendix G: Some Computational Problems583 G.1Graphs583 G.2Boolean Formulae585 G.3Finite Fields, Polynomials, and Vector Spaces586 G.4The Determinant and the Permanent587 G.5Primes and Composite Numbers587 Bibliography589 Index601

……[看更多目录]