中文名: 計算復雜性
作者: Papadimitriou
Leung
Ibe
Sipser
Hopcroft
Motwani
Ullman
BOOLOS
圖書分類: 軟件
資源格式: DJVU
版本: 英文版
出版社: Addison Wesley
書號: 0201530821
發行時間: 1994年
地區: 美國
語言: 英文
簡介:

djvu 閱讀器：
http://windjview.sourceforge.net/
內容簡介：
計算復雜性理論的研究是計算機科學最重要的研究領域之一，而Christos H．Papadmitriou 是該領域最著名的專家之一。本書是一本全面闡述計算復雜性理論及其近年來進展的教科書，主要包含算法圖靈機、可計算性等有關計算復雜性理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等復雜性理論的基礎知識；P與NP、NP完全等各復雜性類的概念及其之間的關系等復雜性理論的核心內容；隨機算法、近似算法、並行算法及其復雜性理論；以及NP之外如多項式空間等復雜性類的介紹。
本書內容豐富，體系嚴謹，證明簡潔，敘述深入淺出，並配有大量的練習和文獻引用。本書不但適合作為研究生或本科高年級學生的教材，也適合從事算法和計算機復雜性研究的人員參考。
內容截圖：


目錄:
PART I:ALGORITHMS
1 Problems and Algorithms
1.1 Graph reachability
1.2 Maximum flow and matching
1.3 The traveling salesman problem
1.4 Notes,references,and problems
2 Turing machines
2.1 Turing machine basics
2.2 Turing machines as algorithms
2.3 Turing machines with multiple strings
2.4 Linear speedup
2.5 Space bounds
2.6 Random access machines
2.7 Nondeterministic machines
2.8 Notes,references,and problems
3 Undecidability
3.1 Universal Turing machines
3.2 The halting problem
3.3 More undecidability
3.4 Notes,references,and problems
PART II:LOGIC
4 Boolean logic
4.1 Boolean Expressions
4.2 Satisfiability and validity
4.3 Boolean functions and circuits
4.4 Notes,references,and problems
5 First-order logic
5.1 The syntax of first-order logic
5.2 Models
5.3 Valid expressions
5.4 Axioms and proofs
5.5 The completeness theorem
5.6 Consequences of the completeness theorem
5.7 Second-order logic
5.8 Notes,references,and problems
6 Undecidability in logic
6.1 Axioms for number theory
6.2 Computation as a number-theoretic concept
6.3 Undecidability and incompleteness
6.4 Notes,references,and problems
PART III:P AND NP
7 Relations between complexity classes
7.1 Complexity classes
7.2 The hierarchy theorem
7.3 The reachability method
7.4 Notes,references,and problems
8 Reductions and completeness
8.1 Reductions
8.2 Completeness
8.3 Logical characterizations
8.4 Notes,referencess,and problems
9 NP-complete problems
9.1 Problems in NP
9.2 Variants of satisfiability
9.3 Graph-theoretic problems
9.4 Sets and numbers
9.5 Notes,references,and problems
10 coNP and function problems
10.1 NP and coNP
10.2 Primality
10.3 Function problems
10.4 Notes,references,and problems
11 Randomized computation
11.1 Randomized algorithms
11.2 Randomized complexity classes
11.3 Random sources
11.4 Circuit complexity
11.5 Notes,references,and problems
12 Cryptography
12.1 One-way functions
12.2 Protocols
12.3 Notes,references,and problems
13 Approximability
13.1 Approximation algorithms
13.2 Approximation and complexity
13.3 Nonapproximability
13.4 Notes,references,and problems
14 On P vs.NP
14.1 The map of NP
14.2 Isomorphism and density
14.3 Oracles
14.4 Monotone circuits
14.5 Notes,references,and problems
PART IV:INSIDE P
15 Parallel computation
15.1 Parallel algorithms
15.2 Parallel models of computation
15.3 The class NC
15.4 RNC algorithms
15.5 Notes,references,and problems
16 Logarithmic space
16.1 The L=NL problem
16.2 Alternation
16.3 Undirected reachability
16.4 Notes,references,and problems
PART V:BEYOND NP
17 The polynomial hierarchy
17.1 Optimization problems
17.2 The hierarchy
17.3 Notes,references,and problems
18 Computation that counts
18.1 The permanent
18.2 The Class P
18.3 Notes,references,and problems
19 Polynomial space
19.1 Alternation and games
19.2 Games against nature and interactive protocols
19.3 More PSPACE-complete problems
19.4 Notes,references,and problems
20 A glimpse beyond
20.1 Exponential time
20.2 Notes,references,and problems
Index
Author index