中文版序言 v
致中国读者 ix
引言 xi
第 1章 原子和虚空 1
第 2章 集合 6
一阶逻辑规则 7
关于非负整数的皮亚诺公理 7
集合论的公理 9
第3章 哥德尔、图灵和他们的小伙伴 15
图灵机 16
额外补充 23
第4章 心智和机器 25
第5章 古复杂性 38
第6章 P、NP和它们的小伙伴 47
第7章 随机性 62
第8章 密码学 80
密码学 81
伪随机数发生器 83
单向函数 86
公钥密码学 87
第9章 量子力学 93
小于0%的可能性？ 95
混合态 99
平方规则 100
实数与复数 102
线性 106
第 10章 量子计算 113
反算 117
与经典复杂性类的关系 118
量子计算和NP完全性问题 124
量子计算和多世界 126
第 11章 彭罗斯 128
打开黑盒子 130
冒险说些显然的事 133
所有人都瞄着这一整块量子“肥肉” 133
第 12章 退相干和隐变量 137
进坑 138
故事一 退相干 140
退相干和热力学第二定律 142
故事二 隐变量 145
“行不通”定理大荟萃 148
隐变量的例子 153
第 13章 证明 160
何为一个证明？ 160
概率证明 162
零知识证明 163
PCP 166
模拟隐变量理论的复杂性 167
第 14章 量子态有多大？ 171
第 15章 量子计算十一诘 185
第 16章 学习 194
第 17章 交互式证明、电路下界及其他 207
交互式证明 208
新进展 218
量子交互式证明 221
第 18章 人择原理趣谈 224
第 19章 自由意志 244
第 20章 时间旅行 258
第 21章 宇宙学和复杂度 273
第 22章 问我什么都行 289
注释 306
致谢 317
