第四章 随机计算与去随机
勘误表
以下页码均以纸质版为准。
| 页码 | 位置 | 类型 | 原文 | 更正 | 致谢 |
|---|---|---|---|---|---|
| 128 | 第三、四行 | 笔误 | \(\mathsf{E}[X_i] = \frac{n-i+1}{n}\) | \(\mathsf{E}[X_i] = \frac{n}{n-i+1}\) | 李昊明 |
| 132 | 定理 4.2 的证明 | 证明错误 | 参见此勘误页面 | 陈晗 | |
| 139 | 引理 4.3 | 笔误 | \(\{x | h(x) = y\}\) | \(\{x \in S | h(x) = y\}\)，其中 \(S\) 满足 \(2^{k-2} \le | S | < 2^{k-1}\) | 毛力源 |
| 147 | 第二行 | 笔误 | 接收 | 接受 | 刘裕炜 |
| 147 | 命题 17 的证明 | 笔误 | \(z_i\) | \(z_j\) | 刘裕炜 |
| 160 | 第二行 | 定义有误1 | \(L \in \mathbf{RL}\) 当且仅当存在对数空间概率图灵机 \(\mathbb{P}\) ... | \(L \in \mathbf{RL}\) 当且仅当存在对数空间多项式时间概率图灵机 \(\mathbb{P}\) ... | |
| 203 | 倒数第七行 | 笔误 | \(\dfrac{\Vert G^{\ell - 1}\mathbf{p} - \mathbf{1} \Vert_2}{\Vert G^{\ell - 1}\mathbf{p} - \mathbf{1} \Vert_2}\cdots\dfrac{\Vert \mathbf{A}\mathbf{p} - \mathbf{1} \Vert_2}{\Vert \mathbf{p} - \mathbf{1} \Vert_2}\) | \(\dfrac{\Vert G^{\ell}\mathbf{p} - \mathbf{1} \Vert_2}{\Vert G^{\ell - 1}\mathbf{p} - \mathbf{1} \Vert_2}\dfrac{\Vert G^{\ell - 1}\mathbf{p} - \mathbf{1} \Vert_2}{\Vert G^{\ell - 2}\mathbf{p} - \mathbf{1} \Vert_2}\cdots\dfrac{\Vert G\mathbf{p} - \mathbf{1} \Vert_2}{\Vert \mathbf{p} - \mathbf{1} \Vert_2}\) | 俞逸洋 |
| 205 | 倒数第四行 | 笔误 | 引理 24 | 命题 24 | 俞逸洋 |
| 210 | 倒数第二行 | 笔误 | \(2\sum_{i < j} G_{i, j}(v_i^2 - v_I^2)\) | \(2\sum_{i < j} G_{i, j}(v_i^2 - v_j^2)\) | 刘裕炜 |
| 227 | 最后一行 | 证明错误 | 参见此勘误页面 | 王文茜 | |
| 234 | 倒数第4行 | 笔误 | 非确定时间图灵机 | 多项式时间非确定图灵机 | 陈蔚骏 |
-
如果 \(\mathbf{RL}\) 不限制运行时间，得到的复杂性类恰好是\(\mathbf{NL}\)。可以参考 https://www.cs.ubc.ca/~condon/cpsc506/handouts/rlog.pdf。但是修改之后本章第 19 题就做不出来了。 ↩