P≠NP問題がざっくり理解できる本

　
＊　追記(6月27日)　最後の紹介した「約数ゲーム」について、メールで解答を教えてくれた人がいたので、最後に追加しました。

　最近、野崎昭弘『「P≠NP」問題』ブルーバックスを読んだので、レビューをエントリーしようと思う。
そもそも、この本を読もうと思ったのは、ある雑誌の企画で「数学の未解決問題」について、ある数学者と討論をすることになっていたのがきっかけだった。ミレニアム問題のいくつかが話題にのぼりそうなので、P≠NP問題についても少し知識を補充しておこうと思ったのだ。
でも、アマゾンのレビューで酷評されているのを読んで、いくぶん躊躇した。それで、少し時間が空いたけど、本屋で立ち読みしてみて、その場で購入した。少なくともぼくには、アマゾンのレビューはミス・ディレクションにすぎないものだとわかった。買って帰って、速攻で読了したが、ぼくの要求にかなった本であった。アマゾンのレビュー欄は、まあ、フリーミアムを利用してサイトに顧客を誘導するための、単なる「釣り」にすぎないコーナーだろう。あそこに労力をかけてdisりを書く精神が理解できない。正直、ご苦労なこったと思う。でも、そろそろ、せめてwikipedia程度の「信憑性チェック」にあたる何かを導入したほうがいいのではないか、と思う。まあ、多くのまともな読者は、アマゾンのレビューは信用しないと思うけど。レビューがひどいので、今回は、楽天のほうにリンクを貼っておく。

「P≠NP」問題 現代数学の超難問 （ブルーバックス） [ 野崎昭弘 ]

アマゾンのレビュアーは、本書がなかなか「P≠NP問題」の本論に入らないことにご不満だったようだ。確かに、「コンピュータとは何ものか」から始まって、全体の半分にあたる100ページぐらいまでコンピュータの歴史とか構造の話をしている。レビュアーは、このことに憤慨している。
ぼくも、このあたりは、斜め読みをしてしまった。知っていることが多く、先を急ぎたかったからだ。でもそれは、単に、ぼくが以前にそういうことを読書した経験があるからにすぎず、「不要だから」ではない。P≠NP問題のキモを理解するのは、やはり、コンピュータの仕組み、例えば、2進法とか計算方式とかチューリングマシンとかを知っているべきだし、また、その歴史を知ることも無駄ではないと思う。本書はそういう派生的な知識を含んでいるが、そうでない本は、息苦しく、素人には楽しみのない苦しいだけの登山道となってしまう。
　野崎さんの名著『不完全性定理』ちくま学芸文庫も、実は、同じ形式をとっていた。数理論理学におけるゲーデルの不完全性定理を解説する本でありながら、全体の半分は、ギリシャ数学の話とか公理系の話とか集合論の話をしている。でも、読了したぼくは、この本で最も重要なのはこの部分なのだ、という感想を持った。ぼくの個人的な感覚にすぎないが、ゲーデルの不完全性定理を素人が理解するために大事なのは、ゲーデル数でもメタ化でも対角線論法でもない、それは「証明するとはどういうことか」「証明の形式化とは何のことなのか」ということだと思うのだ。それを曖昧なままにしておいては、いつまでたっても、不完全性定理のキモを掴むことはできないのではないか、と思う。このことは、専門家には到底想像がつかないだろう。専門家にとって、「証明するとはどういうことか」「証明の形式化とは何のことなのか」ということは、空気のような存在になってしまっているからだ。
ぼくは、野崎さんの『不完全性定理』以前に、何冊かのゲーデル本、例えば、ホフスタッター『ゲーデル・エッシャー・バッハ』などを読んだけれど、不完全性定理のキモがわかった気がしていなかった。だから、何冊も手にすることになったのだ。野崎さんの本を読んで、何がわかっていないのかがわかった。それがまさに、「証明するとはどういうことか」「証明の形式化とは何のことなのか」だった。これがつかめてしまうと、後半になってやっと出てくる、不完全性定理の証明の要約が、あまりにピンときてしまったのだ。もちろん、専門家のようにわかっているわけではない。当たり前だ。数理論理で飯を食っているわけではないので、そんな「完全理解」にさく時間も金も必然性もない。欲しいのは「キモの把握」なのだ。それには、野崎さんの表現で十分だった。この手応えは、その後、数冊の不完全性定理の専門書を読破した現在でも、変わることはない。
　数学の啓蒙書のモットーとすべきは次の四点だと考える。

1.ざっくりとした本質を、誤解を恐れず、日常の言語で示す
2.ベンチマークとなる具体例の投入
3.登山道の道しるべを示す
4.動機付ける

だから、ごちゃごちゃといろんな知識を披露する、とか、読者が挫折するような証明を子細に書く、とか、面白くもない最新の専門的結果を入れる、とかは逆効果で、モットーに反することなのだ。
本書は、ちゃんとこの４つのモットーを叶えている。
第一に、P≠NP問題のPとNPの違いを、ざっくりと、そして、日常表現で表してる。Pは「多項式時間で判定できる問題」を表すのだけど、NPのほうは理解がやっかいで、それは以下のように説明している。

(#1)非決定論的な選択を許す
(#2)計算量は最も良い場合で数える
(#3)答えがNOの場合は、無視してよい
この３つのインチキを許すアルゴリズムで、多項式時間で解けるもの

何冊かの解説書でNPのことを読んだけれど、この説明がもっとも膝を打つものだった。
2.における本書での「ベンチマーク」は、ハミルトン路だ。ハミルトン路とは、点を線で結んだグラフにおいて、すべての点を1回ずつだけ通って出発点に戻るような経路のこと。どんなグラフではそれが可能で、どんなグラフだと不可能なのかを決定するのが、「ハミルトンの問題」である。未解決問題を身近にするには、このような歴史的に有名な問題をベンチマークにするのが得策だと思う。
本書では、このハミルトン路を、NP問題のベンチマークとして、再三説明している。もちろん、どんな計算理論の本にも登場するが、本書ほど丁寧にハミルトン路を説明している本は、少なくともぼくは読んだことがない。本書を読めば、ハミルトン路を見つけるのがなんでやっかいなのかがよくわかる。オイラー路(一筆書き)との違いもよくわかる。ハミルトン路を徹底的にベンチマークとするので、「NP完全」という概念がすんなりと理解できる。
3.の登山道の道しるべも、本書にはちゃんと導入されている。「道しるべ」とは、登山道そのものではない。「もしも登山をするつもりなら、最初にこの道しるべを探し、次にこの道しるべを目指し、とそういうふうに登ればいいのでは？」という示唆を与えてくれることだ。本書を読んだぼくは、「仮に次に何かに進むとするなら」、何を理解すればいいのかがはっきりわかった。NP完全な問題とは、それを決定すれば、NPに属する問題のクラスを完全に決定できてしまう問題のことである。つまり、クラスを代表する問題で、「それだけを分析すればいい」というものだ。例えば、ハミルトン路がそれにあたる。本書によれば、論理式の充足可能性問題(与えられた論理式を真とするような真偽値の割り当てがあるか？)がNPのクラスに属し、しかもP≠NP問題が「充足可能性問題はPに属すか」に帰着されることをクックという人が示したそうだ。つまり、次につまみ食いすべきは、このクックの定理であろうことがわかった。もちろん、つまむかつままないかは、読者の勝手である。このように、本書には、「もう少し精密にP≠NP問題を理解する」ための道しるべが所々におかれているのである。
そして、4.の動機付けについても、本書は十分であると思う。啓蒙書は、読者を「次の啓蒙書に手を出してみよう」とか「専門書を買うだけ買ってみるか」と思わせれば、それだけで成功だ。動機付けとはそういうことである。ぼくは、実際に、本書で動機付けられた。実は、ずいぶん前に、シプサー『計算理論の基礎 1, 2, 3』共立出版を買って本棚に置いてあったが、手つかずのままだった。今回は、野崎さんの本に動機付けられ、この本の3巻を取り出し眺めてみた。そこにはクックの定理の証明が載っており、それを斜め読みして、証明のキモだけは理解することができた。もちろん、精緻に理解したわけではない。当たり前だ。ぼくは専門家ではないので、そんなことをするのは時間と労力の無駄である。趣味と好奇心で、ざっくりと知りたいだけなのである。大事なのは、野崎さんの本を読まなければ、決して、この本を本棚から取り出すことはなく、そして、クックの定理の証明を目にすることもなかった、ということなのだ。
　野崎昭弘『「P≠NP」問題』には、他にも興味深いことがいろいろ書いてあった。例えば、「素数判定」に関して、ルートnまでの素数で割ってみる、というアルゴリズムは指数時間的になってしまうけれど、2002年にインドの3人の数学者によってAKSアルゴリズムというのが発見され、多項式時間で判定できるとわかり、Pのクラスの属する問題だとわかったことがそれだ。ただし、サイズの11次多項式であり、実用的ではないとのことだ。実はぼくは、このAKSアルゴリズムは論文を持っていて、以前にテレビドラマ『相棒』の監修をしたとき、利用した経験がある(この監修については、ドラマ「相棒」シーズン12の第2話「殺人の定理」 - hiroyukikojimaの日記を参照のこと)。利用したときには、「そういう判定法があるんだなあ」と思っただけで、それがP≠NP問題と関係するなどと思っていなかった。
中でも非常に興味深かったのは、最後に「余談」として書いてある、次のゲーム。

1. 最初にある自然数N>1を決める。
2.２人で先手・後手を決め、交互に１つずつ「Nの約数」を言う。
3.どちらかがすでに言った数の約数は、もう言うことができない。
4.他に言う数がなくなり、"N"と言ったほうが負け

このゲームは、先手必勝であることが「それほど難しくなく証明できる」という。しかし、一般的で明快な先手必勝アルゴリズムはまだわかってないとのこと。野崎さんは、これを、「存在する」ことと「具体的に求める」ことのギャップの例として、紹介している。ぼくは、大学の講義でゲーム理論を教えている関係上、こういう面白いゲームの例には非常に興味がある。ちょっと考えてみたけど、今のところ、その「それほど難しくない証明」がわかっていない。「具体的なアルゴリズム」を与えずに「存在」を証明するのだから、きっと「超越的な証明」なのだろう。ウェブで検索してみたんだけど、それらしいものが見つからなかった。誰か知ってたら、教えて欲しい。
　というわけで、P≠NP問題について、前記の４点を備え持った啓蒙書をお探しなら、はい、損はさせません。是非、野崎さんの本を読んでごらんなさい。
　
(追記)上記の最後に紹介した「約数ゲーム」について、「証明」が見られる場所をメールで教えてもらいました。これだから、ネットはすばらしい！
「それほど難しくない」どころか、「すごく簡単な」証明でした。
ここに書いてしまうことも可能だけど、自分で考えたい人もおられるでしょうから、書かないで見られる場所にリンクします。
Conjecture and Proof - Miklós Laczkovich - Google ブックス
の 48 ページです。目次のConstructions Proofs of Existenceをクリックすることで閲覧可能です。
ただし、上記の「どちらかがすでに言った数の約数」を「どちらかがすでに言った数の倍数」に代えたバージョンで説明されています。

不完全性定理 数学的体系のあゆみ ちくま学芸文庫 / 野崎昭弘 【文庫】

【店内全品5倍】計算理論の基礎　3／MichaelSipser／阿部正幸【3000円以上送料無料】