计算复杂性 影印版PDF电子书下载
- 电子书积分:16 积分如何计算积分?
- 作 者:帕帕李米特里乌(PapadimitriouC.H.)著
- 出 版 社:北京:清华大学出版社
- 出版年份:2004
- ISBN:7302089551
- 页数:529 页
PART Ⅰ:ALG?RITHMS 1
1 Problems and Algorithms 3
1.1 Graph reachability 3
1.2 Maximum flow and matching 8
1.3 The traveling salesman problem 13
1.4 Notes,references,and problems 14
2 Turing machines 19
2.1 Turing machine basics 19
2.2 Turing machines as algorithms 24
2.3 Turing machines with multiple strings 26
2.4 Linear speedup 32
2.5 Space bounds 34
2.6 Random access machines 36
2.7 Nondeterministic machines 45
2.8 Notes,references,and problems 51
3 Undecidability 57
3.1 Universal Turing machines 57
3.2 The halting problem 58
3.3 More undecidability 60
3.4 Notes,references,and problems 66
PART Ⅱ:LOGIC 71
4 Boolean logic 73
4.1 Boolean Expressions 76
4.2 Satisfiability and validity 76
4.3 Boolean functions and circuits 79
4.4 Notes,references,and problems 84
5 First-order logic 87
5.1 The syntax of first-order logic 87
5.2 Models 90
5.3 Valid expressions 95
5.4 Axioms and proofs 100
5.5 The completeness theorem 105
5.6 Consequences of the completeness theorem 110
5.7 Second-order logic 113
5.8 Notes,references,and problems 118
6 Undecidability in logic 123
6.1 Axioms for number theory 123
6.2 Computation as a number-theoretic concept 127
6.3 Undecidability and incompleteness 131
6.4 Notes,references,and problems 135
PART Ⅲ:P AND NP 137
7 Relations between complexity classes 139
7.1 Complexity classes 139
7.2 The hierarchy theorem 143
7.3 The reachability method 146
7.4 Notes,references,and problems 154
8 Reductions and completeness 159
8.1 Reductions 159
8.2 Completeness 165
8.3 Logical characterizations 172
8.4 Notes,references,and problems 177
9 NP-complete problems 181
9.1 Problems in NP 181
9.2 Variants of satisfiability 183
9.3 Graph-theoretic problems 188
9.4 Sets and numbers 199
9.5 Notes,references,and problems 207
10 coNP and function problems 219
10.1 NP and coNP 219
10.2 Primality 222
10.3 Function problems 227
10.4 Notes,references,and problems 235
11 Randomized computation 241
11.1 Randomized algorithms 241
11.2 Randomized complexity classes 253
11.3 Random sources 259
11.4 Circuit complexity 267
11.5 Notes,references,and problems 272
12 Cryptography 279
12.1 One-way functions 279
12.2 Protocols 287
12.3 Notes,references,and problems 294
13 Approximability 299
13.1 Approximation algorithms 299
13.2 Approximation and complexity 309
13.3 Nonapproximability 319
13.4 Notes,references,and problems 323
14 On P vs.NP 329
14.1 The map of NP 329
14.2 Isomorphism and density 332
14.3 Oracles 339
14.4 Monot.one circuits 343
14.5 Notes,references,and problems 350
PART Ⅳ:INSIDE P 357
15 Parallel computation 359
15.1 Parallel algorithms 359
15.2 Parallel models of computation 369
15.3 The class NC 375
15.4 RNC algorithms 381
15.5 Notes,references,and problems 385
16 Logarithmic space 395
16.1 The L?NL problem 395
16.2 Alternation 399
16.3 Undirected reachability 401
16.4 Notes,references,and problems 405
PART Ⅴ:BEYOND NP 409
17 The polynomial hierarchy 411
17.1 Optimization problems 411
17.2 The hierarchy 424
17.3 Notes,references,and problems 433
18 Computation that counts 439
18.1 The permanent 439
18.2 The class ⊕P 447
18.3 Notes,references,and problems 452
19 Polynomial space 455
19.1 Alternation and games 455
19.2 Games against nature and interactive protocols 469
19.3 More PSPACE-complete problems 480
19.4 Notes,references,and problems 487
20 A glimpse beyond 491
20.1 Exponential time 491
20.2 Notes,references,and problems 499
Index 509
Author index 519
- 《计算机网络与通信基础》谢雨飞,田启川编著 2019
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《计算机辅助平面设计》吴轶博主编 2019
- 《计算机组成原理解题参考 第7版》张基温 2017
- 《云计算节能与资源调度》彭俊杰主编 2019
- 《Helmholtz方程的步进计算方法研究》李鹏著 2019
- 《微笑 影印本》N.达列基作 1947
- 《计算机组成原理 第2版》任国林 2018
- 《大学计算机信息技术教程 2018版》张福炎 2018
- 《计算机自适应英语语用能力测试系统设计与效度验证 以TEM4词汇与语法题为例》张一鑫著 2019
- 《我和小姐姐克拉拉 7 鹦鹉皮卜 注音版》(德)迪米特尔·茵可夫著;程玮译 2018
- 《被偷走的女孩》(爱尔兰)帕特里夏·吉布尼(Patricia Gibney)著 2020
- 《新手死神 3 摇滚乐队》(英)特里·普拉切特著 2020
- 《特里·哈里森的水彩课 Ⅶ 轻松描绘雪景=TELI HALISEN DE SHUICAIKE Ⅶ QINGSONG MIAOHUI XUEJING》(英)特里·哈里森 2019
- 《牛津通识读本 纪录片》(美)帕特里夏·奥夫德海德著 2018
- 《形体舞蹈训练阐微》乌诺娃编著 2012
- 《预防医学实验指导》乌建平主编 2011
- 《我和小姐姐克拉拉》(德)迪米特尔·茵可夫著;陈俊译 2012
- 《再不疯狂,我们就老了》(澳)塞巴斯蒂安·特里著;刘宏振译 2013
- 《犯罪对策学 下》(苏)米特里采夫,达拉索夫-罗吉奥诺夫主编;中国人民大学刑法教研室译 1955
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《大学生心理健康与人生发展》王琳责任编辑;(中国)肖宇 2019
- 《大学英语四级考试全真试题 标准模拟 四级》汪开虎主编 2012
- 《大学英语教学的跨文化交际视角研究与创新发展》许丽云,刘枫,尚利明著 2020
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《复旦大学新闻学院教授学术丛书 新闻实务随想录》刘海贵 2019
- 《大学英语综合教程 1》王佃春,骆敏主编 2015
- 《大学物理简明教程 下 第2版》施卫主编 2020
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019