計算復雜性

前言

The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience.A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by computability theory, which emerged in the 1930s. This theory focuses on computational tasks, and considers automated procedures （i.e., computing devices and algorithms） that may solve such tasks. In focusing attention on computational tasks and algorithms, computability theory has set the stage for the study of the computational resources （like time） that are required by such algorithms. When this study focuses on the resources that are necessary for any algorithm that solves a particular task （or a task of a particular type）, the study becomes part of the theory of Computational Complexity （also known as Complexity Theory）.1 Complexity Theory is a central field of the theoretical foundations of computer science. It is concerned with the study of the intrinsic complexity of computational tasks. That is, a typical complexity theoretic study refers to the computational resources required to solve a computational task （or a class of such tasks）, rather than referring to a specific algorithm or an algorithmic schema. Actually, research in Complexity Theory tends to start with and focus on the computational resources themselves, and addresses the effect of limiting these resources on the class of tasks that can be solved. Thus, Computational Complexity is the general study of what can be achieved within limited time （and/or other limited natural computational resources）.

內容概要

　　復雜性理論是計算機科學的理論基礎的核心。本書是著名計算機科學家Oded Goldreich的力作，書中對計算任務固有復雜性研究進行了概念性介紹，全面分析了復雜性理論的現代主題?！　”緯婕皬碗s性理論的很多子領域（如難度放大、偽隨機性及概率證明系統(tǒng)等），涵蓋了NP完整性、空間復雜性、隨機性和計數、偽隨機數生成器等內容，還在附錄里面介紹了現代密碼學基礎等?！　”緯鴥热輫乐?，可讀性強，適合作為高年級本科生、研究生的教材。同時，書中展示了復雜性理論的很多子領域，也適合領域專家參考。

作者簡介

Oded Goldreich 以色列魏茨曼科學研究院（Weizmann Institute of Science）計算機科學教授，Meyer W. Weisgal講席教授。他是SIAM Journal on Computing、Journal of Cryptology和Computational Complexity雜志的特約編輯。

書籍目錄

1　Introduction and Preliminaries　1　1.1　Introduction　1　　1.1.1　A Brief Overview of Complexity Theory　2　　1.1.2　Characteristics of Complexity Theory　6　　1.1.3　Contents of This Book　8　　1.1.4　Approach and Style of This Book　12　　1.1.5　Standard Notations and Other Conventions　16　1.2　Computational Tasks and Models　17　　1.2.1　Representation　18　　1.2.2　Computational Tasks　18　　1.2.3　Uniform Models (Algorithms)　20　　1.2.4　Non-uniform Models (Circuits and Advice)　36　　1.2.5　Complexity Classes　42　　Chapter Notes　432　P, NP, and NP-Completeness　44　2.1　The P Versus NP Question　46　　2.1.1　The Search Version: Finding Versus Checking　47　　2.1.2　The Decision Version: Proving Versus Verifying　50　　2.1.3　Equivalence of the Two Formulations　54　　2.1.4　Two Technical Comments Regarding NP　55　　2.1.5　The Traditional Definition of NP　55　　2.1.6　In Support of P Different from NP　57　　2.1.7　Philosophical Meditations　58　2.2　Polynomial-Time Reductions　58　　2.2.1　The General Notion of a Reduction　59　　2.2.2　Reducing Optimization Problems to Search Problems　61　　2.2.3　Self-Reducibility of Search Problems　63　　2.2.4　Digest and General Perspective　67　2.3　NP-Completeness　67　　2.3.1　Definitions　68　　2.3.2　The Existence of NP-Complete Problems　69　　2.3.3　Some Natural NP-Complete Problems　71　　2.3.4　NP Sets That Are Neither in P nor NP-Complete　81　　2.3.5　Reflections on Complete Problems　85　2.4　Three Relatively Advanced Topics　87　　2.4.1　Promise Problems　87　　2.4.2　Optimal Search Algorithms for NP　92　　2.4.3　The Class coNP and Its Intersection with NP　94　　Chapter Notes　97　　Exercises　993　Variations on P and NP　108　3.1　Non-uniform Polynomial Time (P/poly)　108　　3.1.1　Boolean Circuits　109　　3.1.2　Machines That Take Advice　111　3.2　The Polynomial-Time Hierarchy (PH)　113　　3.2.1　Alternation of Quantifiers　114　　3.2.2　Non-deterministic Oracle Machines　 117　　3.2.3　The P/poly Versus NP Question and PH　119　Chapter Notes　121　Exercises　1224　More Resources, More Power　127　4.1　Non-uniform Complexity Hierarchies　128　4.2　Time Hierarchies and Gaps　129　　4.2.1　Time Hierarchies　129　　4.2.2　Time Gaps and Speedup　136　4.3　Space Hierarchies and Gaps　139　Chapter Notes　139　Exercises　1405　Space Complexity　143　5.1　General Preliminaries and Issues　144　　5.1.1　Important Conventions　144　　5.1.2　On the Minimal Amount of Useful Computation Space　145　　5.1.3　Time Versus Space　146　　5.1.4　Circuit Evaluation　153　5.2　Logarithmic Space　153　　5.2.1　The Class L　154　　5.2.2　Log-Space Reductions　154　　5.2.3　Log-Space Uniformity and Stronger Notions　155　　5.2.4　Undirected Connectivity　155　5.3　Non-deterministic Space Complexity　162　　5.3.1　Two Models　162　　5.3.2　NL and Directed Connectivity　164　　5.3.3　A Retrospective Discussion　171　5.4　PSPACE and Games　172　Chapter Notes　175　Exercises　1756　Randomness and Counting　1847　The Bright Side of Hardness　2418　Pseudorandom Generators　2849　Probabilistic Proof Systems　34910　Relaxing the Requirements　416Epilogue　461Appendix A: Glossary of Complexity Classes　463Appendix B: On the Quest for Lower Bounds　469Appendix C: On the Foundations of Modern Cryptography　482Appendix D: Probabilistic Preliminaries and Advanced Topics inRandomization　523Appendix E: Explicit Constructions　545Appendix F: Some Omitted Proofs　566Appendix G: Some Computational Problems　583Bibliography　589Index　60

章節(jié)摘錄

插圖：A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by computability theory, which emerged in the 1930s. This theory focuses on computational tasks, and considers automated procedures （i.e., computing devices and algorithms） that may solve such tasks. In focusing attention on computational tasks and algorithms, computability theory has set the stage for the study of the computational resources （like time） that are required by such algorithms. When this study focuses on the resources that are necessary for any algorithm that solves a particular task （or a task of a particular type）, the study becomes part of the theory of Computational Complexity （also known as Complexity Theory）.1 Complexity Theory is a central field of the theoretical foundations of computer science. It is concerned with the study of the intrinsic complexity of computational tasks. That is, a typical complexity theoretic study refers to the computational resources required to solve a computational task （or a class of such tasks）, rather than referring to a specific algorithm or an algorithmic schema. Actually, research in Complexity Theory tends to start with and focus on the computational resources themselves, and addresses the effect of limiting these resources on the class of tasks that can be solved. Thus, Computational Complexity is the general study of what can be achieved within limited time （and/or other limited natural computational resources）.

媒體關注與評論

“這是一本非常值得關注的書……Goldreich的觀點讓我耳目一新……本書特別注重概念性問題，是研究人員及專家不可或缺的參考文獻?！?　　——M. Bona，佛羅里達大學

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算復雜性 PDF格式下載

---