第1页 / 共632页
第2页 / 共632页
第3页 / 共632页
第4页 / 共632页
第5页 / 共632页
第6页 / 共632页
第7页 / 共632页
第8页 / 共632页
[Computational.Complexity.A.Conceptual.Perspective](Oded.Goldrei....pdf
Cover
Half-title
Title
Copyright
Dedication
Contents
List of Figures
Preface
Organization and Chapter Summaries
Acknowledgments
Charptr 1 Introduction and Preliminaries
1.1 Introduction
1.1.1 A Brief Overview of Complexity Theory
1.1.2 Characteristics of Complexity Theory
1.1.3 Contents of This Book
1.1.3.1 Overall Organization of the Book
1.1.3.2 Contents of the Specific Parts
1.1.4 Approach and Style of This Book
1.1.4.1 The General Principle
1.1.4.2 On a Few Specific Choices
1.1.4.3 On the Presentation of Technical Details
1.1.4.4 Organizational Principles
1.1.4.5 A Call for Tolerance
1.1.4.6 Additional Comments Regarding Motivation
1.1.5 Standard Notations and Other Conventions
1.2 Computational Tasks and Models
1.2.1 Representation
1.2.2 Computational Tasks
1.2.2.1 Search Problems
1.2.2.2 Decision Problems
1.2.2.3 Promise Problems (an Advanced Comment)
1.2.3 Uniform Models (Algorithms)
1.2.3.1 Overview and General Principles
1.2.3.2 A Concrete Model: Turing Machines
1.2.3.3 Uncomputable Functions
1.2.3.4 Universal Algorithms
1.2.3.5 Time and Space Complexity
1.2.3.6 Oracle Machines
1.2.3.7 Restricted Models
1.2.4 Non-uniform Models (Circuits and Advice)
1.2.4.1 Boolean Circuits
1.2.4.2 Machines That Take Advice
1.2.4.3 Restricted Models
1.2.5 Complexity Classes
Chapter Notes
Chapter 2 P, NP, and NP-Completeness
2.1 The P Versus NP Question
2.1.1 The Search Version: Finding Versus Checking
2.1.1.1 The Class P as a Natural Class of Search Problems
2.1.1.2 The Class NP as Another Natural Class of Search Problems
2.1.1.3 The P Versus NP Question in Terms of Search Problems
2.1.2 The Decision Version: Proving Versus Verifying
2.1.2.1 The Class P as a Natural Class of Decision Problems
2.1.2.2 The Class NP and NP-proof Systems
2.1.2.3 The P Versus NP Question in Terms of Decision Problems
2.1.3 Equivalence of the Two Formulations
2.1.4 Two Technical Comments Regarding NP
2.1.5 The Traditional Definition of NP
2.1.6 In Support of P Different from NP
2.1.7 Philosophical Meditations
2.2 Polynomial-Time Reductions
2.2.1 The General Notion of a Reduction
2.2.1.1 The Actual Formulation
2.2.1.2 Special Cases
2.2.1.3 Terminology and a Brief Discussion
2.2.2 Reducing Optimization Problems to Search Problems
2.2.3 Self-Reducibility of Search Problems
2.2.3.1 Examples
2.2.3.2 Self-Reducibility of NP-Complete Problems
2.2.4 Digest and General Perspective
2.3 NP-Completeness
2.3.1 Definitions
2.3.2 The Existence of NP-Complete Problems
2.3.3 Some Natural NP-Complete Problems
2.3.3.1 Circuit and Formula Satisfiability: CSAT and SAT
2.3.3.2 Combinatorics and Graph Theory
2.3.4 NP Sets That Are Neither in P nor NP-Complete
2.3.5 Reflections on Complete Problems
2.4 Three Relatively Advanced Topics
2.4.1 Promise Problems
2.4.1.1 Definitions
2.4.1.2 Applications
2.4.1.3 The Standard Convention of Avoiding Promise Problems
2.4.2 Optimal Search Algorithms for NP
2.4.3 The Class coNP and Its Intersection with NP
Chapter Notes
Exercises
Chapter 3 Variations on P and NP
3.1 Non-uniform Polynomial Time (P/poly)
3.1.1 Boolean Circuits
3.1.2 Machines That Take Advice
3.2 The Polynomial-Time Hierarchy (PH)
3.2.1 Alternation of Quantifiers
3.2.2 Non-deterministic Oracle Machines
3.2.3 The P/poly Versus NP Question and PH
Chapter Notes
Exercises
Chapter 4 More Resources, More Power?
4.1 Non-uniform Complexity Hierarchies
4.2 Time Hierarchies and Gaps
4.2.1 Time Hierarchies
4.2.1.1 The Time Hierarchy Theorem
4.2.1.2 Impossibility of Speedup for Universal Computation
4.2.1.3 Hierarchy Theorem for Non-deterministic Time
4.2.2 Time Gaps and Speedup
4.3 Space Hierarchies and Gaps
Chapter Notes
Exercises
Chapter 5 Space Complexity
5.1 General Preliminaries and Issues
5.1.1 Important Conventions
5.1.2 On the Minimal Amount of Useful Computation Space
5.1.3 Time Versus Space
5.1.3.1 Two Composition Lemmas
5.1.3.2 An Obvious Bound
5.1.3.3 Subtleties Regarding Space-Bounded Reductions
5.1.3.4 Search Versus Decision
5.1.3.5 Complexity Hierarchies and Gaps
5.1.3.6 Simultaneous Time-Space Complexity
5.1.4 Circuit Evaluation
5.2 Logarithmic Space
5.2.1 The Class L
5.2.2 Log-Space Reductions
5.2.3 Log-Space Uniformity and Stronger Notions
5.2.4 Undirected Connectivity
5.2.4.1 The Basic Approach
5.2.4.2 The Actual Implementation
5.3 Non-deterministic Space Complexity
5.3.1 Two Models
5.3.2 NL and Directed Connectivity
5.3.2.1 Completeness and Beyond
5.3.2.2 Relating NSPACE to DSPACE
5.3.2.3 Complementation or NL = coNL
5.3.3 A Retrospective Discussion
5.4 PSPACE and Games
Chapter Notes
Exercises
Chapter 6 Randomness and Counting
6.1 Probabilistic Polynomial Time
6.1.1 Basic Modeling Issues
6.1.2 Two-Sided Error: The Complexity Class BPP
6.1.2.1 On the Power of Randomization
6.1.2.2. A Probabilistic Polynomial-Time Primality Test
6.1.3 One-Sided Error: The Complexity Classes RP and coRP
6.1.3.1 Testing Polynomial Identity
6.1.3.2 Relating BPP to RP
6.1.4 Zero-Sided Error: The Complexity Class ZPP
6.1.5 Randomized Log-Space
6.1.5.1 Definitional Issues
6.1.5.2 The Accidental Tourist Sees It All
6.2 Counting
6.2.1 Exact Counting
6.2.1.1 On the Power of #P
6.2.1.2 Completeness in #P
6.2.2 Approximate Counting
6.2.2.1 Relative Approximation for #Rdnf
6.2.2.2 Relative Approximation for #P
6.2.3 Searching for Unique Solutions
6.2.4 Uniform Generation of Solutions
6.2.4.1 Relation to Approximate Counting
6.2.4.2 A Direct Procedure for Uniform Generation
Chapter Notes
Exercises
Chapter 7 The Bright Side of Hardness
7.1 One-Way Functions
7.1.1 Generating Hard Instances and One-Way Functions
7.1.2 Amplification of Weak One-Way Functions
7.1.3 Hard-Core Predicates
7.1.4 Reflections on Hardness Amplification
7.2 Hard Problems in E
7.2.1 Amplification with Respect to Polynomial-Size Circuits
7.2.1.1 From Worst-Case Hardness to Mild Average-Case Hardness
7.2.1.2 Yao's XOR Lemma
7.2.1.3 List Decoding and Hardness Amplification
7.2.2 Amplification with Respect to Exponential-Size Circuits
7.2.2.1 Hard Regions
7.2.2.2 Hardness Amplification via Hard Regions
Chapter Notes
Exercises
Chapter 8 Pseudorandom Generators
Introduction
8.1 The General Paradigm
8.2 General-Purpose Pseudorandom Generators
8.2.1 The Basic Definition
8.2.2 The Archetypical Application
8.2.3 Computational Indistinguishability
8.2.3.1 The General Formulation
8.2.3.2 Relation to Statistical Closeness
8.2.3.3 Indistinguishability by Multiple Samples
8.2.4 Amplifying the Stretch Function
8.2.5 Constructions
8.2.5.1 A Simple Construction
8.2.5.2 An Alternative Presentation
8.2.5.3 A General Condition for the Existence of Pseudorandom Generators
8.2.6 Non-uniformly Strong Pseudorandom Generators
8.2.7 Stronger Notions and Conceptual Reflections
8.2.7.1 Stronger (Uniform-Complexity) Notions
8.2.7.2 Conceptual Reflections
8.3 Derandomization of Time-Complexity Classes
8.3.1 Defining Canonical Derandomizers
8.3.2 Constructing Canonical Derandomizers
8.3.2.1 The Construction and Its Consequences
8.3.2.2 Analyzing the Construction (i.e., Proof of Theorem 8.18)
8.3.3 Technical Variations and Conceptual Reflections
8.3.3.1 Construction 8.17 as a General Framework
8.3.3.2 Reflections Regarding Derandomization
8.4 Space-Bounded Distinguishers
8.4.1 Definitional Issues
8.4.2 Two Constructions
8.4.2.1 Sketches of the Proofs of Theorems 8.21 and 8.22
8.4.2.2 Derandomization of Space-Complexity Classes
8.5 Special-Purpose Generators
8.5.1 Pairwise Independence Generators
8.5.1.1 Constructions
8.5.1.2 Applications (a Brief Review)
8.5.2 Small-Bias Generators
8.5.2.1 Constructions
8.5.2.2 Applications (a Brief Review)
8.5.2.3 Generalization
8.5.3 Random Walks on Expanders
Chapter Notes
Exercises
Chapter 9 Probabilistic Proof Systems
Introduction and Preliminaries
9.1 Interactive Proof Systems
9.1.1 Motivation and Perspective
9.1.1.1 A Static Object Versus an Interactive Process
9.1.1.2 Prover and Verifier
9.1.1.3 Completeness and Soundness
9.1.2 Definition
9.1.3 The Power of Interactive Proofs
9.1.3.1 A Simple Example
9.1.3.2 The Full Power of Interactive Proofs
9.1.3.3 Sketch of the Proof of Theorem 9.4
9.1.4 Variants and Finer Structure: An Overview
9.1.4.1 Arthur-Merlin Games (Public-Coin Proof Systems)
9.1.4.2 Interactive Proof Systems with Two-Sided Error
9.1.4.3 A Hierarchy of Interactive Proof Systems
9.1.4.4 Something Completely Different
9.1.5 On Computationally Bounded Provers: An Overview
9.1.5.1 How Powerful Should the Prover Be?
9.1.5.2 Computational Soundness
9.2 Zero-Knowledge Proof Systems
9.2.1 Definitional Issues
9.2.1.1 A Wider Perspective: The Simulation Paradigm
9.2.1.2 The Basic Definitions
9.2.2 The Power of Zero-Knowledge
9.2.2.1 A Simple Example
9.2.2.2 The Full Power of Zero-Knowledge Proofs
9.2.3 Proofs of Knowledge -- A Parenthetical Subsection*-0pt
9.2.3.1 Abstract Reflections
9.2.3.2 A Concrete Treatment
9.3 Probabilistically Checkable Proof Systems
9.3.1 Definition
9.3.2 The Power of Probabilistically Checkable Proofs
9.3.2.1 Proving That NPPCP(poly,O(1))
9.3.2.2 Overview of the First Proof of the PCP Theorem
9.3.2.3 Overview of the Second Proof of the PCP Theorem
9.3.3 PCP and Approximation
9.3.4 More on PCP Itself: An Overview
9.3.4.1 More on the PCP Characterization of NP
9.3.4.2 Stronger Forms of PCP-Systems for NP
9.3.4.3 PCP with Super-logarithmic Randomness
Chapter Notes
Exercises
Chapter 10 Relaxing the Requirements
10.1 Approximation
10.1.1 Search or Optimization
10.1.1.1 A Few Positive Examples
10.1.1.2 A Few Negative Examples
10.1.2 Decision or Property Testing
10.1.2.1 Definitional Issues
10.1.2.2 Two Models for Testing Graph Properties
10.1.2.3 Beyond Graph Properties
10.2 Average-Case Complexity
10.2.1 The Basic Theory
10.2.1.1 Definitional Issues
10.2.1.2 Complete Problems
10.2.1.3 Probabilistic Versions
10.2.2 Ramifications
10.2.2.1 Search Versus Decision
10.2.2.2 Simple Versus Samplable Distributions
Chapter Notes
10.2.2.3 Approximation
Exercises
Epilogue
Appendix A Glossary of Complexity Classes
A.1 Preliminaries
A.2 Algorithm-Based Classes
A.2.1 Time Complexity Classes
A.2.1.1 Classes Closely Related to Polynomial Time
A.2.1.2 Other Time Complexity Classes
A.2.2 Space Complexity Classes
A.3 Circuit-Based Classes
Appendix B On the Quest for Lower Bounds
B.1 Preliminaries
B.2 Boolean Circuit Complexity
B.2.1 Basic Results and Questions
B.2.2 Monotone Circuits
B.2.3 Bounded-Depth Circuits
B.2.4 Formula Size
B.3 Arithmetic Circuits
B.3.1 Univariate Polynomials
B.3.2 Multivariate Polynomials
B.4 Proof Complexity
B.4.1 Logical Proof Systems
B.4.2 Algebraic Proof Systems
B.4.3 Geometric Proof Systems
Appendix C On the Foundations of Modern Cryptography
C.1 Introduction and Preliminaries
C.1.1 The Underlying Principles
C.1.1.1 Coping with Adversaries
C.1.1.2 The Use of Computational Assumptions
C.1.2 The Computational Model
C.1.2.1 Efficient Computations and Infeasible ones
C.1.2.2 Randomized (or Probabilistic) Computations
C.1.3 Organization and Beyond
C.2 Computational Difficulty
C.2.1 One-Way Functions
C.2.2 Hard-Core Predicates
C.3 Pseudorandomness
C.3.1 Computational Indistinguishability
C.3.2 Pseudorandom Generators
C.3.3 Pseudorandom Functions
C.4 Zero-Knowledge
C.4.1 The Simulation Paradigm
C.4.2 The Actual Definition
C.4.3 A General Result and a Generic Application
C.4.3.1 Commitment Schemes
C.4.3.2 A Generic Application
C.4.4 Definitional Variations and Related Notions
C.4.4.1 Definitional Variations
C.4.4.2 Related Notions: POK, NIZK, and WI
C.5 Encryption Schemes
C.5.1 Definitions
C.5.2 Constructions
C.5.3 Beyond Eavesdropping Security
C.6 Signatures and Message Authentication
C.6.1 Definitions
C.6.2 Constructions
C.7 General Cryptographic Protocols
C.7.1 The Definitional Approach and Some Models
C.7.1.1 Some Parameters Used in Defining Security Models
C.7.1.2 Example: Multi-party Protocols with Honest Majority
C.7.1.3 Another Example: Two-Party Protocols Allowing Abort
C.7.2 Some Known Results
C.7.3 Construction Paradigms and Two Simple Protocols
C.7.3.1 Passively Secure Computation with Shares
C.7.3.2 From passively Secure Protocols to Actively Secure Ones
C.7.4 Concluding Remarks
Appendix D Probabilistic Preliminaries and Advanced Topics in Randomization
D.1 Probabilistic Preliminaries
D.1.1 Notational Conventions
D.1.2 Three Inequalities
D.1.2.1 Markov's Inequality
D.1.2.2 Chebyshev's Inequality
D.1.2.3 Chernoff Bound
D.1.2.4 Pairwise Independent Versus Totally Independent Sampling
D.2 Hashing
D.2.1 Definitions
D.2.2 Constructions
D.2.3 The Leftover Hash Lemma
D.3 Sampling
D.3.1 Formal Setting
D.3.2 Known Results
D.3.3 Hitters
D.4 Randomness Extractors
D.4.1 Definitions and Various Perspectives
D.4.1.1 The Main Definition
D.4.1.2 Extractors as Averaging Samplers
D.4.1.3 Extractors as Randomness-Efficient Error Reductions
D.4.1.4 Other Perspectives
D.4.2 Constructions
D.4.2.1 Some Known Results
D.4.2.2 The Pseudorandomness Connection
D.4.2.3 Recommended Reading
Appendix E Explicit Constructions
E.1 Error-Correcting Codes
E.1.1 Basic Notions
E.1.2 A Few Popular Codes
E.1.2.1 A Mildly Explicit Version of Proposition E.1
E.1.2.2 The Hadamard Code
E.1.2.3 The Reed--Solomon Code
E.1.2.4 The Reed--Muller Code
E.1.2.5 Binary Codes of Constant Relative Distance and Constant Rate
E.1.3 Two Additional Computational Problems
E.1.4 A List-Decoding Bound
E.2 Expander Graphs
E.2.1 Definitions and Properties
E.2.1.1 Two Mathematical Definitions
E.2.1.2 Two Levels of Explicitness
E.2.1.3 Two Properties
E.2.2 Constructions
E.2.2.1 The Margulis-Gabber-Galil Expander
E.2.2.2 The Iterated Zig-Zag Construction
Appendix F Some Omitted Proofs
F.1. Proving That PH Reduces to #P
F.2. Proving That IP( f ) ⊆ AM(O( f )) ⊆ AM( f )
F.2.1 Emulating General Interactive Proofs by AM-Games
F.2.1.1 Overview
F.2.1.2 Random Selection
F.2.1.3 The Iterated Partition Protocol
F.2.2 Linear Speedup for AM
F.2.2.1 The Basic Switch (from MA to AM)
F.2.2.2 The Augmented Switch (from [MAMA]j to [AMA]jA)
Appendix G Some Computational Problems
G.1 Graphs
G.2 Boolean Formulae
G.3 Finite Fields, Polynomials, and Vector Spaces
G.4 The Determinant and the Permanent
G.5 Primes and Composite Numbers
Bibliography
Index
CUUS063 main CUUS063 Goldreich
978 0 521 88473 0
March 31, 2008
18:49
This page intentionally left blank
CUUS063 main CUUS063 Goldreich
978 0 521 88473 0
March 31, 2008
18:49
Computational Complexity
A Conceptual Perspective
Complexity Theory is a central field of the theoretical foundations of computer science.
It is concerned 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 (and/or with
other limited natural computational resources).
This book offers a conceptual perspective on Complexity Theory. It is intended to serve
as an introduction for advanced undergraduate and graduate students, either as a textbook
or for self-study. The book will also be useful to experts, since it provides expositions of
the various sub-areas of Complexity Theory such as hardness amplification, pseudoran-
domness, and probabilistic proof systems.
In each case, the author starts by posing the intuitive questions that are addressed by the
sub-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 Science
and an Incumbent of the Meyer W. Weisgal Professorial Chair. He is an editor for the
SIAM Journal on Computing, the Journal of Cryptology, and Computational Complex-
ity and previously authored the books Modern Cryptography, Probabilistic Proofs and
Pseudorandomness, and the two-volume work Foundations of Cryptography.
i
CUUS063 main CUUS063 Goldreich
978 0 521 88473 0
March 31, 2008
18:49
ii
CUUS063 main CUUS063 Goldreich
978 0 521 88473 0
March 31, 2008
18:49
Computational Complexity
A Conceptual Perspective
Oded Goldreich
Weizmann Institute of Science
iii
CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
Information on this title: www.cambridge.org/9780521884730
© Oded Goldreich 2008
This publication is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the written permission of Cambridge University Press.
First published in print format
2008
ISBN-13 978-0-511-39882-7
eBook (EBL)
ISBN-13 978-0-521-88473-0
hardback
Cambridge University Press has no responsibility for the persistence or accuracy of urls
for external or third-party internet websites referred to in this publication, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
CUUS063 main CUUS063 Goldreich
978 0 521 88473 0
March 31, 2008
18:49
to Dana
v
CUUS063 main CUUS063 Goldreich
978 0 521 88473 0
March 31, 2008
18:49
vi
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
