目次 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 |