計算量理論の本

以下が私のオススメです。

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