出版社内容情報
原理的な計算可能性の議論から，計算時間を考慮した実際的計算可能性の研究まで平易に解説。〔内容〕準備／チューリング機械／計算量の理論／帰着可能性と完全問題／NPの性質／多項式記憶域計算量／実際的計算可能性／対数記憶域計算量
【目次】
0. 計算量理論への準備
0.1 計算量理論の目標
0.2 集合・関係・写像
0.3 語と半群，形式言語
0.4 自然数と帰納数，アルゴリズム
1. チューリング機械と計算
1.1 チューリング機械
1.2 チューリング機械の機能
1.3 計算可能性と決定問題
1.4 決定不能問題
1.5 停止問題のゲーデル流の証明
2. 計算量の理論
2.1 計算量の概念
2.2 計算機モデル
2.3 計算量理論についての基本定理
3. 帰着可能性と完全問題
3.1 帰着可能性
3.2 完全問題
3.3 NP完全問題
4. NPの性質
4.1 NP完全でないNP問題
4.2 相対化チューリング機械とNP困難な問題
4.3 同型帰着可能性
4.4 多項式時間階層
5. 多項式記憶域計算量のクラス：PSPACE
6. クラスＰと実際的計算可能性
7. 対数記憶域計算量のクラス：LOGSPACE
8. 参考書
9. 索 引
内容説明
本書は、“計算”の定義から始めて、原理的な計算可能性へ、そしてさらに実際的な計算可能性の理論へと進む。あくまで計算機科学の教科書であることを意図しており、記述はそのレベルを超えないようにした。
目次
０ 計算量理論への準備
１ チューリング機械と計算
２ 計算量の理論
３ 帰着可能性と完全問題
４ ＮＰの性能
５ 多項式記憶域計算量のクラス：ＰＳＰＡＣＥ
６ クラスＰと実際的計算可能性
７ 対数記憶域計算量のクラス：ＬＯＧＳＰＡＣＥ
