『「Ｐ≠ＮＰ」問題 現代数学の超難問』

野恕W昭弘 著
講談社ブルーバックス
ISBN978-4-06-257933-9
Ｐ≠ＮＰについて書かれた本。
よく分からないが、個人的には全体としてちぐはぐな印象を受けた。こんなものなのかもしれないが、薦めるには二の足を踏む。
大雑把にいうと、前半は計算量の話、後半がＰ≠ＮＰ予想についての話だが、それがうまくつながっていない印象。Ｐ≠ＮＰについて説明するのに計算量の理解が必要だというのは、分かるけども。
ほかにすることはないのですか、と諸葛亮に言わせてみたい感じ。
こんなものかもしれないので、それでよければ、というところか。
それでもよければ、という本だろう。

以下メモ。
・非決定性アルゴリズムとは、いくつかの選択肢の中から自由に選択でき、その選択はもっとも運のよい（つまりは正解かもしくはそれに近い）ものであり、かつ正解が存在しない場合には選択がうまくいかないが、答えが否だった場合は無視できるようなアルゴリズムであり、そのような非決定性アルゴリズムを使えば多項式時間で解ける決定問題のクラスがＮＰである。
・Ｐは多項式時間で解ける問題のクラスであり、現在のところＮＰでありながらＰに属していないと証明された決定問題は存在せず、Ｐ＝ＮＰであるならば、非決定性アルゴリズムを使えば多項式時間で解ける問題はすべて多項式時間で解けることになる。
・クラスＮＰに属していて、クラスＮＰに属している他のどんな問題のどんな具体例も一般的な手順で多項式時間内でその問題の具体例に翻訳でき、しかも二つの具体例の成否が必ず一致するような問題を、ＮＰ完全という。
・あるＮＰ完全な問題がクラスＰに属していることは、Ｐ＝ＮＰであるための必要十分条件である。
また、ＮＰ完全であればその問題はある意味クラスＮＰの中でもっとも難しい問題であるといえる。