組合せ爆発と、経験則と、暗号化の話。
2012-09-12Mathematics
この動画が最近話題になっています。
この動画では「組合せ爆発」を取り上げています。組合せ爆発というのは、ある問題に対して、考えられる可能性を列挙していくと、その組み合わせが膨大になってしまうことで、動画では、格子をすこしずつ広げながら、スタートからゴールまでの道順を数え上げていますが、格子の一辺の長さが10のときは、もはや単純な方法では数え上げることが事実上不可能であることを示しています。
もう少し具体的な例だと、将棋の思考プログラムなんかも、組合せ爆発を起こします。次に指せる駒のパターンは少なくても、では、3手先、5手先を読むとなると、とたんに可能性が多くなります。この中から最適だと考えられるものをコンピュータは選んで指しますが、これでは、可能性を列挙するだけで時間がかかってしまいます。「考えられる全部の可能性から、最適なものを選ぶ」ということを、その言葉通りに正直にプログラミングしても、コンピュータが計算する時間が長すぎて、使いものにならないんですね。
将棋の場合、3手先、5手先、…、で考えられるすべての盤面の組み合わせのうち、その大半は悪手だったりします。そこで、将棋のプログラムを作成するときは、たとえば振り飛車or居飛車といった戦法のパターンであるとか、囲いの知識、終盤の戦法(詰め方)の知識といったものを利用して、考えられうる盤面のパターンから、指しても無駄なパターンを外す「枝刈り」といわれる工夫をして、効率的に盤面のパターンの数え上げをしています。
将棋の問題も、数学的で論理的な、最適解というものがきっと存在するのだと思いますが、それを求めるとなると、とても時間がかかってしまいます。論理的に正しい解を求めるのが大変な問題に対しては、経験則(将棋でいうと、戦法や囲いなど)を利用して、「ある程度正しい解」を求めることがあります。この経験則を「ヒューリスティクス」といいます。どのような経験則を盛り込むかは、問題を解くためのプログラムを作成する人の「センス」なので、人によって問題の解き方が変わったりして差がでたりするんですね。
さて、組合せ爆発の問題に対して、うまい「経験則」が見つかっていない問題があります。それが「素因数分解」です。素因数分解は、ある整数を素数の積に分解することで、分解できない場合は、それが素数であるとわかります。しかし、現在まで、与えられた整数を、瞬時に素因数分解するための”うまいやり方”というのがありません。素因数分解が難しいことを利用しているのが、暗号化の技術です。
現在、インターネット上で広く使われている「公開鍵暗号方式」は、2つの素数を使用した暗号の方法です。暗号に利用した素数を計算することは、論理的には可能ですが、時間がかかるため、暗号を破るのは非常に大変だ、ということで、その信頼性を得ています。しかし、今後、素因数分解が短時間でできるようになると、この暗号化の方法も使えなくなってしまいます。なお、量子コンピュータを使用すれば、素因数分解は割合早く解くことができることが証明されています。
コンピュータの進化は早いとはいえ、まだまだ難しい問題は、世の中いくらでも転がっているんですね。
Topic
- Mathematics (15)
- Natural Language Processing (1)