P≠NP予想とはなんだろう　ランス・フォートナウ　日本評論社　★★★☆☆

P（polynomial）問題とは、多項式時間で解けるような問題のことである。NP（non-deterministic polynomial）問題とは、解答が与えられたら、その解答が正しいことを多項式時間で検証できるような問題である。NP はnon-polynomialの略ではない。
定義から、P問題はNP問題の部分集合である。P vs NP問題、もしくはP≠NP予想とは、NP問題がP問題の真部分集合である、つまりNPであってPでないような問題が存在するだろうという予想である。
もう一つ、NP完全問題というのがあって、これはP問題であることが示せればすべてのNP問題がP問題であることが示されるようなNP問題のことである。言い換えれば、NP完全問題とは、NP問題のなかで一番難しい問題のことである。
NP完全問題としては、有名な巡回セールスマン問題のほか、数独や地図の塗り分けなど多くの興味深い問題が知られている。
素因数分解は、NP完全問題ではないNP問題だと考えられているが、証明はされていない。一方、ある数が素数かどうかの判定はP問題である。こうしてみると、公開鍵暗号の安全性はそれほど高くはないのかもしれない。

本書は、P問題とNP問題のきちんとした定義を与えることを頑なに拒んでおり、「Pとは、コンピュータを使って素早く解くことができる問題」、「NPは、最良の答を見つけたい問題」などと言っているが、これでは却ってわかりにくい。読んでいてストレスが溜まる。
それから、P=NPであるような世界（おそらく実際はそうでない）が「美しい世界」だというのはどうもピンと来ない。なぜ、NP問題が解けるようになると癌が治癒できるようになるのだろうか？
現状でも、NP問題の近似解ならば実現可能な時間で得ることができる。だから、たとえP=NPであることが証明されて、NP問題の厳密解が得られるようになったとしても、私たちをとりまく世界が革命的に変わるとは思えない。

P=NPを証明することと、NP問題を効率的に（多項式時間で）解くためのアルゴリズムを見つけることは違う。
しかし筆者は、たとえNP問題を解くための実用的なアルゴリズムを見つけ出すことができなくても、ほんの少しだけ効率の良いプログラムを生成するようなプログラムを何度も走らせることによって、最適なアルゴリズムに到達することができると主張する。そうなのかなぁ。

本書には「ゴールデンチケットは見つかるか？」という副題が付いているのだが、これも良い例とは思えない。そもそも、多数のクジの中から当たりを探してくるのは、NPではなくP問題だろう。たとえがアメリカンすぎてわかりにくいこともあるが。（17/10/04読了 21/03/03更新）