P=NP?問題へのアプローチ

P=NP?問題へのアプローチ

西野先生の以前の本「中国人郵便配達問題」が一般向けの本で軽めであったということと比較して，こちらの本はヘビーである．定理もあれば証明もある．一応，計算量理論になじみのない人のためにTuring機械の定義や量子アルゴリズムの定義も書いてあるけれども，初学者には難しく思える．そういうことなので，この本を読もうと思ったら，計算量理論の基礎やアルゴリズムの基礎に対する理解 (これはアルゴリズムが実装できることとは全然違う) を持っていた方がよい．それに加えて，回路計算量理論のところは組合せ論的な論法，量子アルゴリズム・量子計算量理論のところは線形代数的な知識や記法に対する慣れが必要である．
しかし，このような計算量理論専門書は今までなかった (ように思う) ので，なかなか画期的だと思う．これでも回路計算量理論のところで書かれている内容や量子アルゴリズムのところのGroverの結果は今となっては古典的な内容と考えられると思う．

つぶやき．量子計算の一般向け解説本はいろいろ出てるのに，どうして普通の計算 (古典計算) のは全然ないんだろう．