《計算複雜性的現代方法》內容簡介：This book aims to describe such recent achievements of complexity theory in the context of more classical results． It is intended to serve both as a textbook and as a reference for self—study． This means it must simultaneously cater to many audi- ences， and it is carefully designed with that goal in mind． We assume essentiallyno computational background and very minimal mathematical background， which we review in Appendix A．
基本介紹
- 書名：計算複雜性的現代方法
- 作者：阿羅拉(S. Arora)
- 出版日期：2012年1月1日
- 語種：英語
- ISBN：9787510042867
- 品牌：世界圖書出版公司北京公司
- 外文名：Computational Complexity: A Modern Approach
- 出版社：世界圖書出版公司
- 頁數：579頁
- 開本：16
- 定價：99.00
內容簡介,圖書目錄,
內容簡介
《計算複雜性的現代方法》是一部將所有有關複雜度知識理論集於一體的教程。將最新進展和經典結果結合起來，是一部很難得的研究生入門級教程。既是相關科研人員的一部很好的參考書，也是自學人員很難得的一本很好自學教程。本書一開始引入該領域的最基本知識，然後逐步深入，介紹更多深層次的結果，每章末都附有練習。對複雜度感興趣的人士，物理學家，數學家以及科研人員這本書都是相當受益。
圖書目錄
About this book
Acknowledgments
Introduction
0 Notational conventions
0．1 Representing objects as strings
0．2 Decision problems/languages
0．3 Big—oh notation
EXERCISES
PART ONE： BASIC COMPLEXITY CLASSES
1 The computational model——and why it doesn't matter
1．1 Modeling computation： What you really need to know
1．2 The Turing machine
1．3 Efficiency and running time
1．4 Machines as strings and the universal Turing machine
1．5 Uncomputability： An introduction
1．6 The Class P
1．7 Proof of Theorem 1．9： Universal simulation in O（T log T）—time
CHAPTER NOTES AND HISTORY
EXERCISES
2 NP and NP completeness
2．1 The Class NP
2．2 Reducibility and NP—completeness
2．3 The Cook—Levin Theorem： Computation is local
2．4 The web of reductions
2．5 Decision versus search
2．6 coNP， EXP， and NEXP
2．7 More thoughts about P， NP， and all that
CHAPTER NOTES AND HISTORY
EXERCISES
3 Diagonalization
3．1 Time Hierarchy Theorem
3．2 Nondeterministic Time Hierarchy Theorem
3．3 Ladner's Theorem： Existence of NP—intermediate problems
3．4 Oracle machines and the limits of diagonalization
CHAPTER NOTES AND HISTORY
EXERCISES
Soace comlalexitv
4．1 Definition of space—bounded computation
4．2 PSPACE completeness
4．3 NL completeness
CHAPTER NOTES AND HISTORY
EXERCISES
The polynomial hierarchy and alternations
5．1 The Class ∑P2
5．2 The polynomial hierarchy
5．3 Alternating Turing machines
5．4 Time versus alternations： Time—space tradeoffs for SAT
5．5 Defining the hierarchy via oracle machines
CHAPTER NOTES AND HISTORY
EXERCISES
6 Boolean circuits
6．1 Boolean circuits and P/poly
6．2 Uniformly generated circuits
6．3 Turing machines that take advice
6．4 P/poly and NP
6．5 Circuit lower bounds
6．6 Nonuniform Hierarchy Theorem
6．7 Finer gradations among circuit classes
6．8 Circuits of exponential size
CHAPTER NOTES AND HISTORY
EXERCISES
7 Randomized computation
7．1 Probabilistic Turing machines
7．2 Some examples of PTMs
7．3 One—sided and "zero—sided" error： RP， eoRP， ZPP
7．4 The robustness of our definitions
7．5 Relationship between BPP and other classes
7．6 Randomized reductions
7．7 Randomized space—bounded computation
CHAPTER NOTES ANn HISTORY
EXERCISES
Interactive proofs
8．1 Interactive proofs： Some variations
8．2 Public coins and AM
8．3 IP=PSPACE
8．4 The power of the prover
8．5 Multiprover interactive proOfs （MIP）
8．6 Program checking
8．7 Interactive proof for the permanent
CHAPTER NOTES AND HISTORY
EXERCISES
9 Cryptography
9．1 Perfect secrecy and its limitations
9．2 Computational security， one—way functions， and pseudorandom generators
9．3 Pseudorandom generators from one—way permutations
9．4 Zero knowledge
9．5 Some applications
CHAPTER NOTES AND HISTORY
EXERCISES
10 Quantum computation
10．1 Quantum weirdness： The two—slit experiment
10．2 Quantum superposition and qubits
10．3 Definition of quantum computation and BQP
10．4 Grover's search algorithm
10．5 Simon's algorithm
10．6 Shor's algorithm： Integer factorization using quantum computers
10．7 BQP and classical complexity classes
CHAPTER NOTES AND HISTORY
EXERCISES
11 PCP theorem and hardness of approximation： An introduction
11．1 Motivation： Approximate solutions to NP—hard optimization problems
11．2 Two views of the PCP Theorem
11．3 Equivalence of the two views
11．4 Hardness of approximation for vertex cover and independent set
11．5 NP ≤ PCP（poly（n）， 1）： PCP from the Walsh—Hadamard code
CHAPTER NOTES AND HISTORY
EXERCISES
PART TWO： LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS
12 Decision trees
12．1 Decision trees and decision tree complexity
12．2 Certificate complexity
12．3 Randomized decision trees
12．4 Some techniques for proving decision tree lower bounds
CHAPTER NOTES AND HISTORY
13 Communication comDlexitv
13．1 Definition of two—party communication complexity
13．2 Lower bound methods
13．3 Multiparty communication complexity
13．4 Overview of other communication models
CHAPTER NOTES AND HISTORY
EXERCISES
14 Circuit lower bounds： Complexity theory's Waterloo ．
14．1 AC0 and Hastad's Switching Lemma
14．2 Circuits with"counters"： ACC
14．3 Lower bounds for monotone circuits
14．4 Circuit complexity： The frontier
14．5 Approaches using communication complexity
CHAPTER NOTES AND HISTORY
EXERCISES
15 Proof complexity
15．1 Some examples
15．2 Propositional calculus and resolution
15．3 Other proof systems： A tour d'horizon
15．4 Metamathematical musings
CHAPTER NOTES AND HISTORY
EXERCISES
16 Algebraic computation models
16．1 Algebraic straight—line programs and algebraic circuits
16．2 Algebraic computation trees
16．3 The Blum—Shub—Smale model
CHAPTER NOTES AND HISTORY
EXERCISES
PART THREE： ADVANCED TOPICS
……
Appendix： Mathematical background
Hints and selected exercises
Main theorems and definitions
Bibliography
Index
Complexity class index
Acknowledgments
Introduction
0 Notational conventions
0．1 Representing objects as strings
0．2 Decision problems/languages
0．3 Big—oh notation
EXERCISES
PART ONE： BASIC COMPLEXITY CLASSES
1 The computational model——and why it doesn't matter
1．1 Modeling computation： What you really need to know
1．2 The Turing machine
1．3 Efficiency and running time
1．4 Machines as strings and the universal Turing machine
1．5 Uncomputability： An introduction
1．6 The Class P
1．7 Proof of Theorem 1．9： Universal simulation in O（T log T）—time
CHAPTER NOTES AND HISTORY
EXERCISES
2 NP and NP completeness
2．1 The Class NP
2．2 Reducibility and NP—completeness
2．3 The Cook—Levin Theorem： Computation is local
2．4 The web of reductions
2．5 Decision versus search
2．6 coNP， EXP， and NEXP
2．7 More thoughts about P， NP， and all that
CHAPTER NOTES AND HISTORY
EXERCISES
3 Diagonalization
3．1 Time Hierarchy Theorem
3．2 Nondeterministic Time Hierarchy Theorem
3．3 Ladner's Theorem： Existence of NP—intermediate problems
3．4 Oracle machines and the limits of diagonalization
CHAPTER NOTES AND HISTORY
EXERCISES
Soace comlalexitv
4．1 Definition of space—bounded computation
4．2 PSPACE completeness
4．3 NL completeness
CHAPTER NOTES AND HISTORY
EXERCISES
The polynomial hierarchy and alternations
5．1 The Class ∑P2
5．2 The polynomial hierarchy
5．3 Alternating Turing machines
5．4 Time versus alternations： Time—space tradeoffs for SAT
5．5 Defining the hierarchy via oracle machines
CHAPTER NOTES AND HISTORY
EXERCISES
6 Boolean circuits
6．1 Boolean circuits and P/poly
6．2 Uniformly generated circuits
6．3 Turing machines that take advice
6．4 P/poly and NP
6．5 Circuit lower bounds
6．6 Nonuniform Hierarchy Theorem
6．7 Finer gradations among circuit classes
6．8 Circuits of exponential size
CHAPTER NOTES AND HISTORY
EXERCISES
7 Randomized computation
7．1 Probabilistic Turing machines
7．2 Some examples of PTMs
7．3 One—sided and "zero—sided" error： RP， eoRP， ZPP
7．4 The robustness of our definitions
7．5 Relationship between BPP and other classes
7．6 Randomized reductions
7．7 Randomized space—bounded computation
CHAPTER NOTES ANn HISTORY
EXERCISES
Interactive proofs
8．1 Interactive proofs： Some variations
8．2 Public coins and AM
8．3 IP=PSPACE
8．4 The power of the prover
8．5 Multiprover interactive proOfs （MIP）
8．6 Program checking
8．7 Interactive proof for the permanent
CHAPTER NOTES AND HISTORY
EXERCISES
9 Cryptography
9．1 Perfect secrecy and its limitations
9．2 Computational security， one—way functions， and pseudorandom generators
9．3 Pseudorandom generators from one—way permutations
9．4 Zero knowledge
9．5 Some applications
CHAPTER NOTES AND HISTORY
EXERCISES
10 Quantum computation
10．1 Quantum weirdness： The two—slit experiment
10．2 Quantum superposition and qubits
10．3 Definition of quantum computation and BQP
10．4 Grover's search algorithm
10．5 Simon's algorithm
10．6 Shor's algorithm： Integer factorization using quantum computers
10．7 BQP and classical complexity classes
CHAPTER NOTES AND HISTORY
EXERCISES
11 PCP theorem and hardness of approximation： An introduction
11．1 Motivation： Approximate solutions to NP—hard optimization problems
11．2 Two views of the PCP Theorem
11．3 Equivalence of the two views
11．4 Hardness of approximation for vertex cover and independent set
11．5 NP ≤ PCP（poly（n）， 1）： PCP from the Walsh—Hadamard code
CHAPTER NOTES AND HISTORY
EXERCISES
PART TWO： LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS
12 Decision trees
12．1 Decision trees and decision tree complexity
12．2 Certificate complexity
12．3 Randomized decision trees
12．4 Some techniques for proving decision tree lower bounds
CHAPTER NOTES AND HISTORY
13 Communication comDlexitv
13．1 Definition of two—party communication complexity
13．2 Lower bound methods
13．3 Multiparty communication complexity
13．4 Overview of other communication models
CHAPTER NOTES AND HISTORY
EXERCISES
14 Circuit lower bounds： Complexity theory's Waterloo ．
14．1 AC0 and Hastad's Switching Lemma
14．2 Circuits with"counters"： ACC
14．3 Lower bounds for monotone circuits
14．4 Circuit complexity： The frontier
14．5 Approaches using communication complexity
CHAPTER NOTES AND HISTORY
EXERCISES
15 Proof complexity
15．1 Some examples
15．2 Propositional calculus and resolution
15．3 Other proof systems： A tour d'horizon
15．4 Metamathematical musings
CHAPTER NOTES AND HISTORY
EXERCISES
16 Algebraic computation models
16．1 Algebraic straight—line programs and algebraic circuits
16．2 Algebraic computation trees
16．3 The Blum—Shub—Smale model
CHAPTER NOTES AND HISTORY
EXERCISES
PART THREE： ADVANCED TOPICS
……
Appendix： Mathematical background
Hints and selected exercises
Main theorems and definitions
Bibliography
Index
Complexity class index
