計算量理論の本
以下が私のオススメです。
- M・シプサ著、太田・田中監訳『計算理論の基礎』原著第二版(共立出版)平成20年
入門用。極めて丁寧にわかりやすく説明しており、教養課程や文系の学生を含む講義でも十分に使える。第二巻が計算可能性で、第三巻が計算量。
- O. Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge, 2008.
かなり厚い本だが、各事項について「何故そう考えるか」を非常に丁寧に説明してある(これが丁寧すぎてうるさいという評判も多いけれど私は好みです)。私の演習ノートの範囲はこの本の1~6章まででより深く扱っており、7章以降は擬乱数生成、対話証明、平均時計算量など、この本ならではの発展的な話題が、やはり丁寧に解説されている。
- I. Wegener, Komplexitätstheorie, Springer, 2003.
上のGoldreichよりも簡潔な書き方の教科書。非常によく練られた構成で解りやすいと思う。英訳もSpringerから出ている。
- 岩間一雄『アルゴリズム理論入門』(朝倉書店)平成26年(初版平成13年)