『計算量理論 I 〜アルゴリズムの数学的定義から P≠NP 予想まで』 正 誤 ＆ 補 足 表
2020.3.5 現在
| ページ・行 | 誤 or 補足 | 正 | 備考 |
| p.23↑2 | 今世紀 | 前世紀 | 2017.3.31 |
| p.55↑6 | 本書第1巻 | 巻1 | 2017.3.31 |
| 第5章（pp.77〜90） | 参照が??になっている箇所 | 訂正したPDF | 2020.3.5 |
| p.77↓8 | とい言う | という | 2017.3.31 |
| p.107 脚注1 | 解けない(unsolvable)な | 解けない(unsolvable) | 2017.3.31 |
| 第7章 (pp.115〜122) | 算術階層 | 算術的階層 | 2017.5.10 |
| p.116 | 図7.3.1の右側の図 | 訂正した図 | 2020.2.8 |
| 第8章（pp.123〜132） | 参照が??になっている箇所 | 訂正したPDF | 2020.2.8 |
| p.159 脚注13 | 量子の光としての | 量子の波としての | 2017.8.8 |
| p.163↓14〜18 | C, NC, LC | B, NB, LB | 2017.8.20 |
| pp.166〜171 | 10.3.1節を追加 | 追加した内容（PDFファイル） | 2017.8.22 |
| p.179↓2 | シューケース | ショウケース | 2017.3.31 |
| p.193 | 11.5.2項を追加 | 追加した内容（PDFファイル） | 2017.3.31 |
| p.197↑4 | 本書第2巻 | 本書の巻II | 2017.3.31 |
| p.200↓5 | y の個数 | y の個数（y を x の解と呼ぶ） | 2017.4.20 |
| p.200↑11,13; p.201 定理12.4(b) | #HAMILTON | #HAMILTON-PATH （ハミルトン道の個数） | 2017.4.20 |
| p.201↓3 | A, Bを数え上げ問題 | A⊂Σ*, B⊂Δ* を数え上げ問題を符号化した言語 | 2017.4.20 |
| p.201↓4 | #還元 | 脚注を追加 | 2017.4.20 |
| p.201↓6 | x が A のインスタンスなら f(x) は B のインスタンス | x∈A ⇔ f(x)∈B | 2017.4.20 |
| p.201↓17 | Cook-Levinの定理 | クック・レヴィンの定理 | 2017.4.20 |
| p.202 ↓115 | 末尾に文を追加 | サイクルの重みとは，サイクル上の辺の重みの積のことである． | 2017.4.20 |
| p.203 定理12.5 | 参照文献を追加 | 追加した参照文献 | 2017.4.20 |
| p.203 定理12.5の証明の中 | (x_i, \bar{m}) | <x_i, \bar{m}> （x_i と \bar{m} のペアの符号化） | 2017.4.20 |
| p.204 | 定理12.5の証明の直後 | 1文と問を追加（追加した内容＝ピンクの部分） | 2017.4.20 |
| p.204+1 | 12.2.4項を追加 | 追加した内容 | 2017.4.23 |
| p.204+4 | 12.2.5項を追加 | 追加した内容 | 2017.4.30 |
誤植や誤りの連絡やご意見等をお寄せ下さる場合は moriya@waseda.jp 宛てにお願いします。
