補足説明
紙面の都合上,本の中では書ききれなかったこともあります.その中でも本書中で 「Web」 記されている項目について,以下で補足説明をします.
☆基本命令のみでアニメーション (p.24)
本書では「基本命令でもいろいろなことができる」,「アニメーションだって作ることもできる」と豪語したが,実際にはページ数等の都合でその例をお見せすることができなかった. その具体例を「授業ページ」の課題1で紹介しているので参照して興味のある方は参照して欲しい.
☆コンピュータ内でのデータ表現法(p.38)
作成中(10月末に公開予定).
☆プログラミング言語 Ruby の補足(p.62)
本書ではプログラムの例として Ruby というプログラミング言語で書いたプログラムを紹介している.けれども,言語 Ruby での書き方自体の説明は大幅に省略している. ごくごく基本ではあるが,「授業ページ」の課題1や課題2の中で紹介しているので参照して興味のある方は参照して欲しい.(ページは,現在作成中.10月公開予定.)
☆読者への課題の解答(p.140)
電話でコイン投げをするプロトコルの説明で
このプロトコルの最初の重要な点は,Kちゃんが,後で p×q が x に等しく,しかも p, q が素数であることを確かめる点である.(脚注: でも,なぜ,素数性を確かめなければならないのだろうか?これは読者への課題としておこう.)と書かれているが,なぜ素数性を確かめなければならないのだろうか?それは,p, q が素数でないと,もしかすると x = u×v となるような 別の u, v があって,それを使うとKちゃんが負けるように答えられるかもしれないからである.p, q が素数であれば,一通りにしか分解できないのでKちゃんも安心なのである.
☆P≠NP予想について(p.164)
本書でも説明したが,P≠NP予想についてのもう少し詳しい解説は, 著者の解説ページ P≠NP予想って何?を参照して頂きたい.
さらに少し追加を以下に述べよう:P≠NP予想は「NP問題の中には本当に計算が難しいものが存在する」ということだが,しばしば,「それを数学的に証明したとして何が嬉しいの?」と問われることがある.難しいことが(スパコンなど使ってもとても歯が立たない計算問題があるということが)わかって何が嬉しいの?ということだ.ある意味ごもっともな話である.
本書でも述べているように,「歯が立たない」ことが暗号の安全性を保証する場合もある.けれども,それは実際にP≠NP予想を研究する意義のほんの一部である.そのことを著者が悟ったのは,正直なところ比較的最近のことなのだ.この研究に関するプロジェクト「計算限界解明(科研費新学術領域)」を始めてからなのである.少し長くなるが,その「悟り」に到達したいきさつを述べよう.
ある日の鎌倉でのことである.「計算限界解明」ではプロジェクトのアドバイザとして, 計算の理論の著名な研究者であるLance Fortnow(ランス・フォートナウ)ジョージア工科大教授を招いた.その彼を鎌倉見物に連れていったときのことである.大仏を見た後のある喫茶店でのこと.彼が急に,「Osamu,もしP=NPだったらどんなにすばらしいか考えてみよう」(注:元は英語)と言い出した.そうして,こんなこともできる,あんなこともできる,と話し出したのである.我々専門家ならば熟知していることなのに,と思いつつも,そうした空想に付き合っているうちに,話が大いに盛り上がってしまったのである.(お蔭で,鎌倉観光は大仏のみで,あとはその喫茶店に夕方までずっといました...)その中で,「あっ,人類はP=NPの世界を望んでいるし,目指しているのだね!」と思い至ったのである.
もちろん,P≠NPのはずである.けれども,すべてのNP問題が難しいわけではない.さらには,難しいNP問題であっても,そのすべての問題例を解く万能なアルゴリズムがないだけで,十分攻略できる問題例も多い(むしろ,ほとんどがそう)かもしれない.しかも,それら問題例の中には,解を見つけることが世のため人のためになることが数多くあるのだ.そうした攻略法を見出すために,なぜP≠NPなのかを明らかにし,どこに難しさがあるのか,どこならば攻略できそうなのかを明らかにすることが重要なのである.そこにこそP≠NP予想を研究する価値があるのである.
ちなみに,P=NPを目指しても,暗号など情報セキュリティ技術の基礎になるNP問題は「歯が立たない」状況でいて欲しい,という虫のよい世界を私たちは希望している.そちらの意味でも,どの問題例には「隙がない(つまり歯が立たない)」かを見抜く方法が必要である.
フォートナウ氏は,来日の少し前にP≠NP予想に関する一般向けの本「The Golden Ticket: P, NP and the Search for the Impossible」(邦訳:P≠NP予想とはなんだろう,ゴールデンチケットは見つかるか?)を出版していた.今から考えると,彼は単にその本の話をしたのかったかもしれない. ということで,私が大いに盛り上がってしまって自ら「悟った」気になっているのに,もしかしたら戸惑っておられたかもしれない.この周辺を三十年ちかく研究してきて,そうした意義を知らなかったわけではない.けれども,それを正面切って議論したことで,心にきっちり収まった気持ちになれたのは事実であり,だからこそこうして皆さんにも語れるようになったのである.私にとっては大変よい収穫であった.