計算量理論を学ぶための演習問題です。東大での演習や京大での集中講義で使ったものをもとに、独習できるよう少し説明を加えたので公開します。通常の教科書よりも簡素な説明ですが、自力で解き進めることで要点をむしろ短時間で深く理解できることを目指しています。
高校数学のほかに特段の予備知識は要らない積りですが、基本的な算法(アルゴリズム)についての少し素養があった方が読み易いかもしれません。解答はありませんがメールで質問を頂ければ答えます(どこの学生さんでも遠慮なくどうぞ)。随時改訂していますので、細かい誤りの御指摘から、「ここがわからなかった」「○○についての説明は?」など、御意見・御感想を頂ければ幸いです。