つい一この前（2007年10月23日）のことである。ポアンカレ予想を解いたペレルマンの番組がNHKで放映された。番組の趣旨は多分、フィールズ賞も辞退し今どこで何に没頭しているかわからない男すなわち「難問に取り憑かれた数学者の神秘性」をえぐり出すということだと思う。で、ポアンカレ予想を解いたとは、それが真なることを証明したということだ。この問題自体は面白い問題で、このサイエンス・エッセイの一つ「
奇数のオイラー数？」と
その続編と多少関係があるのだが、ここでお話するのはそのことではない。実はポアンカレ予想にかなり肉薄していた何人かの一人、ハーケン(Wolfgang Haken)が番組に登場したのだ。この顔、見覚えがある、としばらく考えて思い出した。４色問題をアペル(Kenneth Appel)とともに解決した人だ。番組ではペレルマンをもり立てる脇役的な存在だったが、とんでもない。４色問題を解いた偉人である。
４色問題とは「どんな地図も４色で塗り分けられる」という予想で、これが正しいかどうか長い間、多分フェルマーの大定理ほど長くはないと思うが、わからなかった。それが1978年正しいことが証明されたのだ。当時、証明されたこと自体より、コンピューターを駆使した力ずくの証明の「美しくなさ」が物議をかもした。美しくないということは、それより重要なことであるが、話がそれだけに閉じていて、他の数学の問題や一般論への適用に寄与しないということだ。それ自体素晴らしい音楽であるとともに以後の音楽に決定的かつ持続的影響を及ぼしたドビュッシーの音楽と逆で、他と何のつながりもない一発勝負の特異点のようなものだ。
さて少しは自分で考えたことを書こう。それが表題の「３色問題と印鑑証明」だ。実は「４色問題と印鑑証明」でも成り立つのかもしれないが。
さて４色問題は証明されたが、３色で塗り分けられない地図はいくらでもある。そこで「与えられた地図が３色で塗り分けられるかどうか」はどうやったら判定できるだろう？ これはやってみるしかない。やってみて運良く３色で塗り分けられたら「塗り分けられる」と判定できるが、塗り分けられない場合は、１回や２回の試行では断言できない。あらゆる色の順番でどう塗り分ける努力をしてもできないことを言わなければならない。そのためには、一体どれだけの試行回数が必要なのだろう？ 実は国の数がｎ個のとき、ｎに対して指数関数で発散する回数が必要であることがわかっている。そのような問題を非Ｐ型（Polynomial＝多項式＝程度の発散でおさまらない問題）と呼ぶが、この「３色塗り分け判定問題」はさらにその中でも重要な「ＮＰ完全問題」と呼ばれる問題に属する。要するにｎをちょっと増やしただけでもうコンピューターでも解けなくなってしまう問題なのだ。
であるならば、これを印鑑証明に使えるはずだ。たとえば次のようにすればよいのではないか、というアイデアだ。まず国をランダムに描き足して白地図を作って行く。このとき３色で塗り分けられるように、まずは色を付けて描き足す。いい加減何百という国を描いたら、そこで色を抜いて白地図にする。この地図をあなたの印鑑として市役所に登録するのだ。目的は、後日市役所に行って「私はその地図を作製した本人です。その証拠に、作製者本人しかできない３色塗り分けを実行してみせます」と言って本人証明するのだ。ＮＰ完全問題なのだから、答えを知らない人はどんなに時間をかけてもできない。しかし作ったあなたならできるというわけだ。
大ざっぱには以上だが、実はここでもう一ひねり要る。応対に出た市役所の職員が善人とは限らない。（昨今いろんな事件がありますからね） あなたが塗り分けた方法を覚えて、後日あなたになりすまして預金を引き出すかもしれない。そこであなたは、３色塗り分けの仕方を悟られないようにそれを証明しなければならない。これを一般にゼロ知識証明という。いわば「私は重大なことを知っている。その内容を明かさずに、知っているという事実を証明してみせよう」というわけだ。今の場合どうやってやるか？ これは次のように可能である。可能であるという事実の中身に立ち入りたい人は続けて読まれたい。
たとえば赤青黄の３色に塗り分けた地図にジグソーパズルのように国ごとに蓋をして、市役所の職員には任意の隣り合った２つの国だけ色を見てもらい、異なる色で塗り分けられていることを確認してもらう。次に、赤青黄の順番を適当に変えて同じように蓋をし、また任意の２つの国だけ見てもらう。これを十分多数回繰り返すと、もしあなたが作成者本人でなければどこかでボロを出し同じ色の隣国を職員に発見されてしまう。しかし十分多数回やって常に異なる色の隣国ばかりだったら、市役所の職員は指数関数的に小さな危険率で本人認証できたと納得する。
市役所の職員がどんなに記憶力が良くて幼児みたいにトランプの神経衰弱に強かったとしても、３色塗り分け法を盗み見ることは不可能だ。毎回ご破算で色の使い方がリセットされているから。こうして市役所の職員は、３色塗り分け法を知ることなく、あなたがそれを知っていることを納得せざるを得ないわけだ。
先に「４色でもいけるかも」と書いたが、それは「４色でどうやったら塗り分けられるか」を見つけることが非Ｐ型問題ならばよいが、そうであるかどうかを私は知らない。知っている人がいたら教えて欲しい。しかし３色塗り分けの方が難しいのだから、この「印鑑証明」の実用性は３色の方が優れているように思われる。
この記事で一つ言いたかったのは次のようなことである。まず、何かが「出来る、あるいは出来ない」ことの証明は、基本として最も重要である。しかしその証明には、特に出来ることの証明の方であるが、「どうやったら出来るか」に触れられないことがある。むしろそんな具体的な方法に言及せずに間接的に「出来る」ことを証明する方がカッコいい。まして「この例についてはこうやれば出来る」などというのは数学的にはカッコ悪い。しかし特殊例について「こうやったら出来る」という方法があるなら、それを使っても実用上は相当面白いことができるということである。
ポアンカレ予想からは離れてしまったが、それもまたよし、としよう。
［最終稿：2007年10月25日］
前ページ（サイエンス・エッセイ）に戻る
ホームに戻る