P ≠ NPの証明で今週のインターネットは大騒動に, でも結局だめだったよう
Twitterなどオンラインコミュニティの連中が、専門家に先がけて科学的発見を云々し始めると、どういうことになるか？ 今週起きたそれは、数学的証明にはほど遠いゴミとして捨てられるようなものをめぐる、膨大な空騒ぎだった。
コンピュータ科学者たちはずいぶん前から、有意義な計算問題でも計算に要する時間が長すぎて事実上解けないものがたくさんある、と考えていた。数十年前には、大量にあるこのような問題…NP問題〔or, ‘NP完全問題’〕と呼ばれる…の共通の性質として、そのうちのたった一つに対する高速解が見つかれば実はそれがすべての問題に対する高速解である、ということが発見された。でも、そういう解を誰も見つけられないまま年月が過ぎ去り、今では数学者たちの標準的な仮説として、解は見つからないとされている。
しかし数学者は、仮説ではなく証明がないと満足しない。そして、NP問題には高速解がないことを証明しようとして、長年いろんな人が努力してきた。計算機の特質を生かして高速解の得られる問題をP問題と呼ぶので、この証明は「“P ≠ NP”の証明」と呼ばれる。PはNPではない、だからNP問題には高速解がない、という意味だ。長年証明者が現れないので、今や、正しい証明にはClay Mathematics Instituteが100万ドルの賞金を用意している。
この前の日曜日（米国時間8/8）に、HPの研究社員Vinay Deolalikarが、同社としては二人目の、インターネットインスタント有名人現象の犠牲者になった。彼は自分の個人的なWebサイトにP ≠ NPを証明する試行を投稿し、発表のメールを送った。そのメールをこの問題を最初に公式化したStephen Cookが読み、Cookはそのメールを何人かの親しい数学者たちに転送した。転送には、今では不名誉となった声明文: “これはP vs NPを解いたと称するかなり真剣な主張と思われる”が添付された。
Cookの認定メールのせいで、Deolalikarの論文をいくつかの研究者のブログが取り上げ、さらにHackerNewsや一般のマスコミも取り上げた。数学のアマチュアも専門家もその論文をブログのコメントやその後の投稿でぼろくそに批判し、重大な欠陥を指摘した。TwitterやFacebook、あるいはソーシャルなニュース集積サイトがないころには、P ≠ NPのような難しい問題の論文の草案は、厳しい学術的な過程を経て、証明の正しさや誤り修正の可否が判定されたのだが。
Deolalikarの証明草案は1日だけ一般公開され、その後、あらゆる方向から袋たたきに遭った。彼にメールをしたら、自動返信で “私のメールは今たいへん混雑しています。お返事の遅れをお許しください”と言ってきた。ご冗談を。“論文の最終バージョンを準備中です。それはJournal Reviewに提出されるでしょう”という但し書きもあるが、証明の欠陥をめぐる細かい議論は今も続いている。
何が重要か？ PはNPでない、の実用的な意味合いは、アルゴリズムの中には計算に相当な長時間を要するものもあるので、そのことを利用した暗号関数は比較的安全である、ということになる。もしもP=NPなら、数学を変えてしまうし、私たちの世界観も変わる。これまで難しいと考えられていた計算問題の多くが、解けるようになる。たとえば、巡回セールスマン(Traveling Salesman)問題、グラフの色分け(Graph Coloring)問題などだ。多くの大型コンピュータがNP問題の解に挑戦しているが、今のところ不満足な解しか生み出していない。
もしかして、本誌のライターや読者にも、数学オタクの資質があるのかな？
（翻訳：iwatani(a.k.a. hiwa)）
近日開催のイベント
