総集編 No.3

鼎談の表紙へ， 鼎談のあらすじへ， キーフレーズから見た鼎談へ，

３．１．ＣＳの一例：アルゴリズムの研究

おっけい．渡辺さんに，もっと具体的なことを語ってもらいましょう． 私は，それはプログラミングの技術論ではないのかとか， それは数学の一部ではないかと，ちゃちゃを入れることにします．

あえて，悪役担当．本当は心やさしい人だってころを，二人は知っているよね．

心やさしい根上さんに，悪役をさせるのは心が痛む．

う，う，う．（感動に涙している．）

具体的な話に入るのは賛成です． まずは「計算」の重要な側面である，アルゴリズムの話にしましょうか？ でも，どんな話題がいいですか？

では，私から．簡単な例を使って，私のちゃちゃの入れ方を示しましょう．

たとえば素数の判定方法を考えてみましょう． 単純に，与えられた数 n が素数かどうかを判定するには， 2 から n-1 までの数で順に割っていって， 割り切れるかどうかを判定するればよいですね．

でも，これだと，10000 くらいの数の素数性を判定するのに， 約 10000 回の割り算の判定をすることになる． そこで，もっと早くできないだろうかと，よーく考えてみる． すると， n が √n より大きい数で割り切れるならば， √n より小さい数ですでに割り切れている． これに気付けば， 割り切れるかどうかの判定は， √n 以下の数に対して行えばよいことになります．

要するに，単純な素数判定アルゴリズムの計算量は O(n) だったけれど， 後の方は O(√n) になって，ずっと早くなった．

それはそれでいいのだけれど， アルゴリズムを速くしようという思いは「技術論」のような気がするし， √n 回の割り算でよいという理解は数学だと思います． つまり， 「数学的な理解をプログラムに応用してみました」 という構図になっているわけですが， このどこにコンピュータ・サイエンスの「基礎」が隠れているのでしょうか？

根上さんのあげた例では，コンピュータ・サイエンスが見えにくいですね． 確かに「数学的な理解をプログラムに応用してみました」という構図です．

でも，与えられた自然数 n の素数性を判定するのに √n に比例するような時間がかかっていては， とても暗号システムなどには使えません． 実は，log n に比例する程度の時間で，ほぼ確実に判定する方法があるのです． これは Miller-Rabin test と呼ばれている手法で，なかなかおもしろいものです．

折角ですから簡単に説明しましょう． これは，与えられた自然数 n, k に対するある種のテスト MR(n,k) を使います （ただし，1 < k < n）． このテスト MR(n,k) の値は 0 か 1 です． また，大雑把に言って，log n に比例する程度の時間で計算できます． さて肝心な点は次の性質です．

n が素数 ⇒ すべての k に対して MR(n,k) = 0． n が合成数（素数でない）⇒ 半数以上の k に対して MR(n,k) = 1．

この性質から次のような素数判定法が考えられます． これが Miller-Rabin test です．

Miler-Rabin test for the primarity： 素数性を判定したい数を n とする． 2 から n - 1 の k を d 個ランダムに選んで M(n,k) を計算する． 計算した結果，1 つでも M(n,k) = 1 となる k があれば合成数， すべて 0 ならば素数と判定する． ＊ d は十分大きければ適当な数で構わない．たとえば d = 10 で十分．

この判定法だと O(log n) の計算時間で素数判定ができるのです．

さて， 本論に戻りましょう． MR(n,k) が上記の性質を持つことを示すには整数論の結果などを使います． しかし MR(n,k) 自体は，整数論では考えなかったでしょう． これは，素数判定アルゴリズムを作りたい，というところから，考え出されたテストなのです．

この MR(n,k) の設計（とその正当性の証明）自体は， 本格的な整数論の議論からすれば，かなり簡単なことでしょう． でも，あくまでも効率的なアルゴリズムを作るために「数学している」わけで， 「数学を応用している」わけではないのです．

ところで，この手法では「ほぼ確実に」でしか判定できません． とくに，合整数を素数と言い誤る可能性があります． つまり，「素数」と判定されても，完全に正しいとは限りません． 一方，「合成数」という判定は完全に信じることができます．

では，これと対称的なアルゴリズムが作れないでしょうか？ つまり，「素数」という判定は，完全に信じることができるようなアルゴリズムです． （一方，「合成数」と言われても，完全には信じられなくてもよいとします．）

この問題は，長いこと未解決だったのですが， 数年前に Adleman が学生さんとともに解いたと 発表しています． ただ，議論が複雑で，論文も 300 ページに及ぶとのことで， 証明を完全に理解している人は， ほとんどいないという噂です．

こうなってくると，完全に「アルゴリズムの開発を目指した理論」ということになってきます． 私は， こうした研究を， 数学ではなくコンピュータ・サイエンスだと主張したいのです．

「アルゴリズムの開発を目指した理論」というのは， いわゆる純粋数学と違う雰囲気を持っていると私も思います． でも「応用を目指した数学」と呼ぶこともできますよね． これは大括りしすぎなのでしょうか．

３．２．アルゴリズムの研究も立派な「純粋数学」ですよ！？

うーん． 「いわゆる純粋数学とは違う雰囲気」，逆に，「純粋数学の雰囲気」というのは何でしょうね． （それを体感しようと，瞑想している．．．）

パチッ（瞑想から覚めた音）

私も，渡辺さんが教えてくれた素数判定の話は， 「応用」ではなくて「基礎研究」だと思います． でも，やっぱり数学なのではないでしょうか？

そのアルゴリズムの正当性に決着をつけるのがものが何なのか，と考えると， やはり数学的な原理なのではないですか？ 数学は，そういう原理を提供してくれるから「基礎科学」なのでしょう． そして，その原理だけで演繹できることを研究するのが，「純粋数学」ですよね．

だとすると，数学的原理以外の何かが追加されていないと， その素数判定の研究は，やはり「純粋数学」の仲間ということになるのでは？ 普通の人が「純粋数学」という言葉からイメージするものではないかもしれませんが， 私は，素数判定の研究を「純粋数学」の仲間にいれても，全然，違和感がありませんよ．

渡辺さんが最初に予言したように， コンピュータ・サイエンスから新しい基礎科学が誕生するのだとすると， きっと，「数学的原理」でも「物理法則」でもない何かがあるはずです．

それが何なのかを知りたいですね． 素数判定の話を煮詰めていくことで，それが何なのかが見えてこないでしょうか？

従来の数学では，

人の目から（現時点では）隠されている知識を明らかにする

という動機付けが多いのにたいして， 素数判定の話の動機付けが

（社会的必要などから）解かねばならない問題がある

となっている事は特徴的な気がします．

３．３．「計算」を対象としているところがＣＳの新しさ

なるほど．そういう見方もありますね． 多分，多くの人（数学者も含めて）の見方はそんなところなのでしょうか． 少し意地悪な言い方ですが， たとえ根上さんが「それは数学」と思っても， そう思わない人たちが主流なのではないでしょうか． だから「応用数学」という名称も出てくるわけです．

ただ，誤解を避けるために補足すると， 世の中の要請などの問題意識が先にあるから純粋数学なのではない， というだけの議論では，まだ，表層的です．

ここで，私が主張したいのは，単なる世の中の受け取り方ではなく，質の違いです． 素数判定のアルゴリズムを考えることの根本にあるのは， 「計算にはどのくらいの能力があるのか？」という疑問だと思います． もう少し抽象的に言うと，限られた有限種類の演算を組み合わせて， どれだけのことができるのか，さらには，どれくらい効率良くできるのか， という疑問が根底にあります．

こうした「計算」を核にした学問がコンピュータ・サイエンスなのです． この核の存在が，従来の数学とは違った学問を形成する可能性を秘めているのだと思います．

まあ，素数判定の話が数学なのか，数学でないのかは，いずれ決着させることにしましょう．

いずれにしても， 「計算」を核にして世の中にあるものを見るという行為は， コンピュータ・サイエンスが産み出した新しい観点だと私も思います．

それで，その観点をより明確にするのは， 「どのくらい効率をよくできるか」ではなくて， 「どのくらい効率をよくできないか」という問いかけなのではないですか？

そうそう，「どのくらい効率良くできないか？」という問いは重要です． 「計算」について議論するときの出発点になるでしょう． それはまた， アルゴリズムのよさを議論するときの尺度としても必要ですね．

話がちょっとそれますが，企業の方と研究すると， 「どのくらい効率をよくできないか」という問いかけの研究が理解されない事があります．

現場にとっては「問題が解ければＯＫ」という事が多いのですが， 「解ければＯＫ」というスタイルで皆が研究をすると， 自分の方法の「良さ」を主張するだけで， 互いの意志疎通ができないのですけどね．

事例研究の論文集などで， 「自分のはいいんだ！」と叫ぶ大会になってしまっているのをときどき見かけますよね．

そうそう．

松井さんの話を聞いて， 「自己主張」と「自己表現」という言葉が，私の頭の中を走りました． 単にアルゴリズムを工夫して効率を上げただけの研究だと， 「自分のはいいんだ！」と主張せざるをえない． でも， 究極の真理に到達してしまうと， 「自分のはいいんだ！」と主張しなくても，自分が見たものを表現するだけでいい．．．

基礎科学の求めるものは， 「表現」であって，「主張」ではないわけです．

==> ７月の鼎談へと続く

鼎談の表紙へ， 鼎談のあらすじへ， キーフレーズから見た鼎談へ，