オートマトン言語理論計算論 2 第2版

8 テューリング機械入門(コンピュータで解けない問題 テューリング機械 ほか) 9 決定不能性(帰納的可算でない言語 帰納的可算な決定不能問題 ほか) 10 実行不能な問題(クラスPとクラスNP 最初のNP完全問題 ほか) 11 その他の「問題のクラス」(NPに属す言語の補集合 多項式領域で解ける問題 ほか)