2014年2月11日火曜日

『四色問題』/ロビン・ウィルソン



素数の音楽』に引き続いて新潮文庫のScience & History Collectionシリーズに手を出してみました。

正直、あんまり面白くなかった……。

「四色問題」というのは「どんな地図でも四色あれば塗り分けられるか?」という問題なんですけど、図形というか組み合わせというか、すごく苦手な分野。

素数やフェルマーの最終定理は難しい証明部分がさっぱりわからなくても楽しめたけど、こちらはなんか、その証明過程や数学者の苦闘にあまりわくわくしない。

なので、あんまり書くことがない(笑)。

1879年にケンプという人が一旦「証明完了!」と発表して、11年に亘って「正しい」と思われてきた。ところが1890年、ヘイウッドという人がその証明の不備に気づく。

彼の序文は、ケンプの論文の間違いを発見してしまったことを詫びているようにさえ見える。 (P186)

「正しい」と思われてきたものを覆すのって、勇気が要りますものね。ケンプさんまだ生きてたし。

で、ヘイウッドさんはケンプさんの間違いを正すことはできなかったものの、「五色定理」は証明することができた。

「五色あれば、どんな地図でも隣り合う国々が違う色になるように塗り分けることができる」

四色より色数が一つ増えているとはいえ、「どんな地図でも」、どれだけ複雑な、どれだけ国の数が多い地図でも「たった五色」で塗り分けれられる、というのはなかなかすごいことです。

ホントかよ?

と、反例になるような複雑怪奇な地図を書いてみたくなりますよね。

その後、「四色問題」の方も証明されて「四色定理」となるわけですが、その証明の過程は「どんな地図でも」の部分をいかに小さくできるか、ということのような。

読んでてもあんまり頭に入ってこなかったので自信はないですが、「不可避集合」とか「可約配置」をどうこう、というのは要するに「生成可能な地図(境界の区切り方)のパターンはこれだけしかない」ということを示して、「このパターンはより簡単なこのパターンに変換でき、返還後のパターンは四色で塗り分けられる」ということを積み上げればいい、ということかと。

巻末の用語集によると

【不可避集合(配置の)】その中の少なくとも一つがすべての地図に現れるような配置の集合。最も簡単な例は、一個の二辺国、三辺国、四辺国、五辺国からなる。

【可約配置】最小反例には含まれない様な国々の配置。ある地図が可約配置を含んでいるとき、これを覗いた残りの地図が四色で塗り分けられるなら、必要に応じて塗り直しをすることで、四色の塗り分けを地図全体に拡張することができる。

ということだそう(…わかったようなわからんような…)

最後に用語集と年表がついてるの、いいなぁと思いました。こうしてあとで振り返る時大変助けになる。

「四色問題」の証明は最後、そういう可約配置とか不可避集合の計算をコンピュータが担って、

コンピュータの使用時間は1000時間に達した。証明には一万点の図が含まれ、コンピュータの出力紙を床に積み上げた高さは4フィート(約1.2メートル)にもなった。 (P318)

そうです。

証明が発表されたのは1976年。コンピュータの処理速度はまだ遅くて、十分な記憶容量もなく、そもそもコンピュータの台数が少なく、そうそう使わせてもらえない中、がんばって計算させたとか。

それが今では「家庭用コンピュータで3時間以内に確認できる」。

技術の進歩ってすごいというか、逆にありがたみなくなったなっていうか(笑)。

で、この「コンピュータによる証明」というのが発表当時物議を醸したそうで、「そんなもん証明とは言えん!」という態度の人も多かったとか。

果たして「証明」とは何なのか。とりわけ、コンピュータが登場してしまった「現代の証明」とは。

コンピュータによる証明は「人間の手ではチェックできない」と言っても、「フェルマーの最終定理」や「ポアンカレ予想」の証明となると、それが人間の手でなされたものとはいえ、別の人間が正しいかどうかを「検証」するのは非常に大変で、「同じことではないか」とも思える。

なので、現在では「コンピュータによる証明は証明と認めない」なんてことはないようです。

ただ、「エレガントな数学」でないことは確かで、「コンピュータを使わない四色問題の証明を誰もが待ち望んでいた」けれど、現在に至るまでそのような画期的なアイディアは登場していない。

まぁ一応「証明終了!」を宣言されてしまった問題を、「僕ならもっと美しく解ける!」と引き続きいじくり回すというのはなかなか難しいですよね。やっぱり、「まだ誰も解いたことのない問題」を解いた人間になる方が楽しいでしょう。


というわけで、私にはいまいちでしたが、図形とか配置とか好き!って方は読んでみるといいかも(投げやりな終わり方ですいません)。

0 件のコメント:

コメントを投稿