中文版序言 v 致中國讀者 ix 引言 xi 第 1章 原子和虛空 1 第 2章 集合 6 一階邏輯規(guī)則 7 關(guān)于非負(fù)整數(shù)的皮亞諾公理 7 集合論的公理 9 第3章 哥德爾、圖靈和他們的小伙伴 15 圖靈機(jī) 16 額外補(bǔ)充 23 第4章 心智和機(jī)器 25 第5章 古復(fù)雜性 38 第6章 P、NP和它們的小伙伴 47 第7章 隨機(jī)性 62 第8章 密碼學(xué) 80 密碼學(xué) 81 偽隨機(jī)數(shù)發(fā)生器 83 單向函數(shù) 86 公鑰密碼學(xué) 87 第9章 量子力學(xué) 93 小于0%的可能性？ 95 混合態(tài) 99 平方規(guī)則 100 實(shí)數(shù)與復(fù)數(shù) 102 線性 106 第 10章 量子計(jì)算 113 反算 117 與經(jīng)典復(fù)雜性類的關(guān)系 118 量子計(jì)算和NP完全性問題 124 量子計(jì)算和多世界 126 第 11章 彭羅斯 128 打開黑盒子 130 冒險(xiǎn)說些顯然的事 133 所有人都瞄著這一整塊量子“肥肉” 133 第 12章 退相干和隱變量 137 進(jìn)坑 138 故事一 退相干 140 退相干和熱力學(xué)第二定律 142 故事二 隱變量 145 “行不通”定理大薈萃 148 隱變量的例子 153 第 13章 證明 160 何為一個(gè)證明？ 160 概率證明 162 零知識(shí)證明 163 PCP 166 模擬隱變量理論的復(fù)雜性 167 第 14章 量子態(tài)有多大？ 171 第 15章 量子計(jì)算十一詰 185 第 16章 學(xué)習(xí) 194 第 17章 交互式證明、電路下界及其他 207 交互式證明 208 新進(jìn)展 218 量子交互式證明 221 第 18章 人擇原理趣談 224 第 19章 自由意志 244 第 20章 時(shí)間旅行 258 第 21章 宇宙學(xué)和復(fù)雜度 273 第 22章 問我什么都行 289 注釋 306 致謝 317