計算理論の本を読み終わった。 難しすぎて7割くらいしか理解出来なかったが、計算理論というものがどういうものか、その全体像は理解出来た気がする。

自分はTuring-completeとかをあまりちゃんとやっていなかったので、 その辺を一通りちゃんとやりたい、と思ってこの本を読んだのだが、 そういう期待値以上のものだった。 P vs NPやTuring completeなどの話題の他に、線形計画法やrandomized algorithmやMCMCのmixingなどもあり、 計算にまつわる事が非常に幅広く扱われている。しかも各分野相当突っ込んだ事までやる。

特にrandomized algorithmは奥が深く、現代数学って感じで久しぶりに数学の深淵を覗いた気持ちになった。 専門じゃないのにここまで最近の議論についていけるのは、この著者の非凡な才能を示していると思う。 この著者はこの問題をめちゃくちゃよく理解しているのだろうね。ビビる。

この本は計算可能性やその複雑さという視点で、その周辺の話題をすべて扱った本と思う。 読み物的に書かれているが通常は証明無しで「XXXだという事が知られている」程度で終わらせるような高度な内容も、 割とちゃんと証明のあらすじを解説していくので、 そこらの真面目な教科書よりも遥かに難しい。 というかこの手の教科書の中ではダントツで一番難しいんじゃないか。 2000年代に知られるようになった事までちゃんと扱うので、この手の理論としては最先端と言って良い話題が並ぶ。 そんな内容なので、当然専門家じゃないと厳しいものがかなり含まれる。

後半の各章は、章の最後の1/5くらいはそういう難しい話題となっているので、自分はほとんど理解出来なかった。 ただ各章のトピックのうち前半はそれなりにちゃんと消化出来て、 前半を消化出来ていると最後の方が何をやっているのか、くらいはわかるようになる。 だからその章で扱っている現代的な議論の概要くらいはつかめるようになる。

数学として要求されるモノは多岐に渡り、グラフ理論や群論などはかなり詳しくないと各章の後半は全く分からない。 自分はグラフ理論はかなり詳しい方だと思うがそれでもExpander周りは全然ついていけなかった。群論はそんなに詳しくないので不足だらけだった。 最後の量子コンピュータは相当量子力学詳しくないと全く太刀打ちできないと思う。 自分は昔大学でやった程度の知識しかなくて全く理解出来なかった。

ただそれだけの内容なので、一通り読むと計算理論という分野に関してはもう十分理解した、という気にはなる。 この分野のそれぞれのトピックの専門家になろうと思ったら何をやらなきゃいけないか、という事も明確になったし、 計算理論のそのほかの教科書を目次を中心に立ち読みしてもだいたい何を扱っているかは分かる。 この本一冊やればこの分野はもういいか、と思えるだけの内容だった。 良い勉強になったと同時に、良い知的な刺激を受けた。