| 目次 i |
| Preface to the Japanese Edition iii |
| 翻訳にあたって xi |
| まえがき |
| 第0章 序論 1 |
| 0.1 オートマトン,計算可能性,複雑さ 1 |
| 複雑さの理論 1 |
| 計算可能性の理論 2 |
| オートマトン理論 3 |
| 0.2 数学的概念や用語 4 |
| 集合 4 |
| 列と組 6 |
| 関数と関係 8 |
| グラフ 11 |
| 文字列と言語 15 |
| Boole論理 16 |
| 数学的な語句の要約 18 |
| 0.3 定義,定理,証明 19 |
| 証明の発見 19 |
| 0.4 証明のタイプ 23 |
| 構成的証明 23 |
| 背理法 24 |
| 帰納法 25 |
| 演習と問題 28 |
| 第1部:オートマトンと言語 31 |
| 第1章 正規言語 33 |
| 1.1 有限オートマトン 33 |
| 有限オートマトンの形式的な定義 37 |
| 有限オートマトンの例 39 |
| 計算の形式的な定義 43 |
| 有限オートマトンの設計 44 |
| 正規演算 47 |
| 1.2 非決定性 51 |
| 非決定性有限オートマトンの形式的な定義 57 |
| NFA と DFAの等価性 59 |
| 正規演算の閉包性 64 |
| 1.3 正規表現 68 |
| 正規表現の形式的な定義 69 |
| 有限オートマトンとの等価性 72 |
| 1.4 非正規言語 84 |
| 正規言語に対するポンピング補題 84 |
| 演習と問題 91 |
| 第2章 文脈自由文法 99 |
| 2.1 文脈自由文法 100 |
| 文脈自由文法の形式的な定義 102 |
| 文脈自由文法の例 104 |
| 文脈自由文法の設計 105 |
| 曖昧性 106 |
| Chomsky の標準形 108 |
| 2.2 プッシュダウン・オートマトン 111 |
| プッシュダウン・オートマトンの形式的な定義 113 |
| プッシュダウン・オートマトンの例 114 |
| 文脈自由文法との等価性 117 |
| 2.3 非文脈自由言語 126 |
| 文脈自由言語に対するポンピング補題 127 |
| 演習と問題 132 |
| 第2部:計算可能性の理論 137 |
| 第3章 Church-Turing の提唱 139 |
| 3.1 Turing 機械 139 |
| Turing 機械の形式的な定義 142 |
| Turing 機械の例 145 |
| 3.2 Turing 機械の変型 151 |
| 複数テープTuring機械 152 |
| 非決定性Turing機械 154 |
| 列挙装置 157 |
| 他のモデルとの等価性 158 |
| 3.3 アルゴリズムの定義 159 |
| Hilbertの問題 159 |
| Turing機械を記述するための用語 162 |
| 演習と問題 164 |
| 第4章 判定可能性 169 |
| 4.1 判定可能な言語 170 |
| 正規言語に関連する判定可能問題 170 |
| 文脈自由言語に関連する判定可能問題 174 |
| 4.2 停止問題 178 |
| 対角線論法 180 |
| 停止問題の判定不可能性 185 |
| Turing認識不可能な言語 188 |
| 演習と問題 189 |
| 第5章 帰着可能性 193 |
| 5.1 言語理論における判定不可能問題 194 |
| 計算履歴を用いた帰着 199 |
| 5.2 単純な判定不可能問題 207 |
| 5.3 写像帰着可能性 214 |
| 計算可能な関数 215 |
| 写像帰着可能性の形式的な定義 215 |
| 演習と問題 220 |
| 第6章 計算可能性の理論における先進的な話題 223 |
| 6.1 再帰定理 223 |
| 自己参照 224 |
| 再帰定理のための用語 228 |
| 応用 228 |
| 6.2 数理論理における判定可能性 231 |
| 判定可能な理論 234 |
| 判定不可能性の理論 237 |
| 6.3 Turing帰着可能性 240 |
| 6.4 情報の定義 242 |
| 最小長記述 243 |
| 定義の最適性 247 |
| 圧縮不可能な文字とランダム性 248 |
| 演習と問題 251 |
| 第3部:複雑さの理論 255 |
| 第7章 時間の複雑さ 257 |
| 7.1 複雑さの測定 257 |
| big-O記法とsmall-o記法 259 |
| アルゴリズムの解析 261 |
| モデル間の複雑さの関係 265 |
| 7.2 クラスP 268 |
| 多項式時間 269 |
| Pに属する問題の例 271 |
| 7.3 クラスNP 277 |
| NP に属する問題の例 282 |
| P vs.NP問題 285 |
| 7.4 NP完全性 286 |
| 多項式時間帰着可能性 287 |
| NP 完全性の定義 292 |
| Cook-Levinの定理 292 |
| 7.5 他のNP完全問題 300 |
| 頂点被覆問題 301 |
| Hamilton パス問題 302 |
| 部分和問題 309 |
| 演習と問題 |
| 第8章 領域の複雑さ 319 |
| 8.1 Savitchの定理 322 |
| 8.2 クラスPSPACE 325 |
| 8.3 PSPACE完全 326 |
| TQBF問題 327 |
| ゲームの必勝法 332 |
| 一般化された「しりとり」ゲーム 334 |
| 8.4 クラスLとクラスNL 341 |
| 8.5 NL完全性 344 |
| グラフ中の検索 346 |
| 8.6 NLとcoNTの等価性 348 |
| 演習と問題 351 |
| 第9章 問題の扱いにくさ 355 |
| 9.1 階層定理 356 |
| 指数領域完全性 365 |
| 9.2 相対化 371 |
| 対角線論法の限界 373 |
| 9.3 回路の複雑さ 376 |
| 演習と問題 386 |
| 第10章計算の複雑さの理論における先進的な話題 389 |
| 10.1 近似アルゴリズム 389 |
| 10.2 確率的アルゴリズム 392 |
| クラスBPP 392 |
| 素数性 396 |
| 一回読み出し分岐プログラム 402 |
| 10.3 交替性 407 |
| 交替性時間と交替性領域 408 |
| 多項式時間階層 413 |
| 10.4 対話証明系 414 |
| グラフの非同型性 415 |
| モデルの定義 416 |
| IPとPSPACEの等価性 417 |
| 10.5 並列計算 430 |
| 一様Boole回路 430 |
| クラスNC 432 |
| P完全性 435 |
| 10.6 暗号 436 |
| 秘密鍵 437 |
| 分開鍵暗号系 438 |
| 一方向性関数 439 |
| 落し戸関数 441 |
| 演習と問題 443 |
| 参考文献 445 |
| 欧文索引(対訳付) 453 |
| 和文索引(対訳付) 470 |
| 目次 i |
| Preface to the Japanese Edition iii |
| 翻訳にあたって xi |
図書
図書
