《Computational Complexity A Conceptual Perspective_Oded Goldreich》pdf电子书免费下载
下载方式一：
百度网盘下载地址：https://pan.baidu.com/s/1dgM4cK8AI55yR1IXG0582w
百度网盘密码：1111
下载方式二：
http://ziliaoshare.cn/Download/af_123678_pd_ComputationalComplexityAConceptualPerspective_OdedGoldreich.zip
|
|
作者：empty 页数：632 出版社：empty |
《Computational Complexity A Conceptual Perspective_Oded Goldreich》介绍
Complexity Theory is a central field of the the or etal foundations of computers cic nceIt i sconce med with the general study of the intrinsic complexity of computational tasks；that is， it addresses the question of what can be achieved within limited time f and/or withother imited natural computational resources)This book offers a conceptual perspective on Complexity Theory.It is intended to serveas an introduction for advanced undergraduate and graduate students， ci the rasa textbookor for self-study The book will also he useful to experts， since it provides expositions ofthe various sub-areas of Complexity Theory such as hardness amplification， pseudo ran-dom ness， and prabilistic proof systemsIn each case， the author starts by posing the intuitive questions that are addressed by thesub-area and then discusses the choices made in the actual formulation of these questions，the approaches that lead to the answers， and the ideas that are embedded in these answers.Oded Goldreich is a Professor of Computer Science at the Weizmann Institute of Scienceand an Incumbent of the Meyer W.We is gal Professorial Chair.He is an editor for theSIAM Journal on Computing， the Journal of Cryptology， and Computational Complex-ity and previously authored the books Modern Cryptography， Prabilistic Proofs andPseudorandom tness， and the two-volume work Foundations of Cryp log ru phy
《Computational Complexity A Conceptual Perspective_Oded Goldreich》目录
Contents
List of Figures
Preface
page xii
Organization and Chapter Summaries
Acknowledgments
1 Introduction and Preliminaries
1.1 Introduction
1.2 Computational Tasks and Models
Chapter Notes
2P.NP， and NP-Completeness
2.1ThePVersusNP Question
A Brief Overview of Complexity Theory
Characteristics of Complexity Theory
Contents of This Book
Approach and Style of This Book
Standard No lations and Other Conventions
Representation
Computational Tasks
Uniform Models(Algorithms)
Non-uniform Models(Circuits and Advice)
Complexity Classes
The Search Version：Finding Versus Checking
The Decision Version：Proving Versus Verifying
213Equivalence of the Two Formulations
2.1.4Two Technical Comments Regarding NP
2.1.5The Traditional Definition of NP
2.1.6In Support of P Different from NP
2.1.7Philosophical Meditations
2.2Polynomial-Time Reductions
2.3NP-Completeness
2.4Three Relatively Ady anced Topics
Chapter Notes
Exercises
3 Variations on P and NP
3.1Non-uniform Polynomial Time(P/poly)
3.2The Polynomial-Time Hierarchy(PH)
Chapter Notes
Exercises
4 More Resources， More Power?
4.1Non-uniform Complexity Hierarchies
4.2 Time Hierarchies and Gaps
4.3SpaceHicrarchicsandGaps
Chapter Notes
Ex crc is es
5 Space Complexity
5.1General Preliminaries and Issues
5.2Logarithmic Space
5.3Non-deterministic Space Complexity
The General Notion of a Reduction
Reducing Optimization Problems to Sc arch Problems
Self-Reducibility of Search Problems
Digest and General Perspective
Definitions
The Existence of NP-Complete Problems
Some Natural NP-Complete Problems
NP Sets That Are Neither in Pn or NP-Complete
Ref icc tions on Complete Problems
Promise Problems
Optimal Search Algor thms for NP
The Class coN PandIts Intersection with NP
Boolean Circuits
Machines That Take Advice
Alternation of Quantifiers
Non-deterministic Oracle Machines
The P/poly Versus NP Question and PH
Time Hierarchies
Time Gaps and Speedup
Important Conventions
On the Minimal Amount of Useful Computation Space
Time Versus Space
Circuit Evaluation
The Class L
Log-Space Reductions
Log-Space Uniformity and Stronger Notions
Undirected Connectivity
Two Models
NL and Directed Connectivity
A Retrospective Discussion
Probabilistic Polynomial Time
6.1.1Basic Modeling Issues
Counting
Chapter Notes
Ex crc is es
7 The BrightSide of Hardness
7.1One-Way Functions
7.2 Hard Problems in E
Chapter Notes
Exercises
8 Pseudorandom Genera for s
Introduction
8.1 The General Para dgm
Two-SidedError：TheComplexityClassBPP
Onc-SidedError：TheComplexityClassesRPandcoRP
Zero-Sided Error.The Complexity Class ZPP
Randomized Log-Space
Exact Counting
Approximate Counting
Searching for Unique Solutions
Uniform Generation of Solutions
Generating Hard Instances and One-Way Functions
Amplification of Weak One-Way Functions
Hard-Core Predicates
Reflections on Hardness Amplification
Amplification with Respect to Polynomial-Size Cir eu its
Amplification with Respect to Exponential-Size Circuits
Non-uniformly Strong Pseudorandom Generators
Stronger Notions and Conceptual Reflections
Technical Variations and Conceptual Reflections
On Computationally Bounded Provers：An Overview
Proofs of Knowledge-A Parenthetical Subsection
The Power of Probabilistically Checkable Proofs
General-Purpose Pseudorandom Generators
8.2.1The Basic Definition
8.2.2The Archetypical Application
8.2.3Computational Indistinguishability
8.2.4Amplifying the Stretch Fun e tion
8.2.5Constructions
8.3.1Det in ing Canonical De randomizers
8.3.2Constructing Canonical De randomizers
8.4.1Definitional Issues
8.4.2Two Constructions
8.5.1Pairwise Independence Generators
8.5.2Small-Bias Generators
8.5.3RandomWalks on Expanders
9.1.1Motivation and Perspective
9.1.2Definition
9.1.3The Power of Interactive Proofs
9.1.4Variants and Finer Structure：An Overview
9.2.1Definitional Issues
9.2.2The Power of Zero-Knowledge
9.3.1Definition
9.3.3PCP and Approximation
9.3.4Morc on PC Plt self.An Overview
10.1.1 Search or Opti ization
10.1.2 Decision or