P≠NP予想とは

どうも体調がスッキリしないので(そういえば去年も1月は体調が悪かった気が…この時期は駄目なのかな?)、アウトドアの機会は少ないです。 外には居るけど、じーっと列車待ちでほとんど動いていないのは気にしない。 

インドアの話となると「何があるかな?」と思案した結果、何故か数学ネタが増えてきています。誰も読んでくれないだろうなーと思っていたのですが意外と反響があったので、調子に乗って次のネタを書く事にしました。



昨今のAI(人工知能)の進化は凄まじく、人間を上回るのは時間の問題に思えます。では「コンピュータはいつの日にか、あらゆる問題に一瞬で答えを出せる日が来るのか?」という疑問が出てきます。それが今回取り上げる「P≠NP予想」に繋がります。

PとかNPとは何ぞや?ですが、少々噛み砕いて説明してみます。

今、日本全国の鉄道路線図を渡されたとします。路線図を基に最長片道切符の旅を計画するとしましょう。同じ駅を二回通らず、できるだけ長い距離を乗ってくださいという問題です。管理人のように鉄道にキョーミない人にはサッパリ分からない問題です(ん?)。



P問題とは「多項式時間で解ける判定問題」です…と言っても、何の事か???だと思います。

ある問題が与えられた時、その問題が難しいかを客観的に評価するための指標としてサイズnという値を定義します。上記の最長片道切符旅を考える場合ならば、nは駅の数と考えられます(※正確には中間駅は考慮不要ですが)。

例えば、n=2ならば2都市間です。東京~大阪ならば「東海道新幹線に乗る」「中央線~関西線に乗る」…など、いくつかの選択肢が出てきますが、まだ考えやすそうです。

これがn=100になったらどうでしょうか。東京~上野~大宮~高崎~…~米原~京都~大阪など、考える経路が増えてきて大変そうに思えます。

実際に考えるべき問題はここまで単純ではないのですが、今は概要を知ってもらうために「n=2の時は2秒」「n=3の時は3秒」「n=100の時は100秒」で「正解はコレコレです。」とコンピュータが短時間(多項式時間)でズバリ正解を導き出してくれるとしましょう。

今は単純に比例としましたが、実は「n=2の時は2×2=4秒」「n=3の時は3×3=9秒」「n=100の時は100×100=10,000秒」といったような形(より正確にはnのk乗の形、すなわち多項式)でも構いません。このような問題をP問題と呼びます。

n=100の時で既に大差があるように見えますが、これはあくまで極端にした例である事をご承知おきください。これぐらいならばコンピュータには許容範囲で朝飯前と言えます。



一方、NP問題とは何か?「東京~上野~大宮~高崎~…~米原~京都~大阪の最短経路はこうだと思います。」という答えの候補が与えられた時にその答えは正しいです(または間違っています)、とコンピュータがズバリ回答してくれる問題の事です。

…は?同じ事言ってるんじゃないの?

と思えますが、よーく見るとビミョーに異なっているのです。思いっきり大雑把な説明になりますが

P問題
「私コンピュータが、何もヒントがない所から最短最良の方法で答えに辿りついてあげましょう!」です。先入観がない状態と言えます。

NP問題
「何だよこの回答、どう見ても間違ってるじゃねぇかよ…。でも、言われたからには私コンピュータが調べない訳にはいかないでしょうね。メンドクサイなーブツブツ…。」です。

さぁ、ここでP≠NP予想に辿りつきます。

「面倒なNP問題も、上手いやり方をしてやればP問題と同じように考えられるんじゃないの?」と考えた方はP=NP賛成派と言えます。

「面倒なNP問題はやっぱり面倒で、どう頑張ってもP問題のように簡単に解く事はできないんじゃないの?」と考えた方はP≠NP賛成派と言えます。

さぁ、現在はどう考えられているか?P≠NP予想という名前から薄々お気づきの方もおられるかもしれませんが、後者と考える研究者が多いのが実情です。「これだけNP問題を大勢で突っつき回しているのに簡単に解く方法を見つけたという話はついぞ聞かない、やはり難しい問題は難しいのだ!」という事です。

一見するとP≠NPは不幸な事のように思えますが、必ずしもそうとは言い切れません。その例としてよく出てくる暗号の例を挙げましょう。インターネットでやり取りされる情報は実は誰でも傍受する事が容易なのですが、暗号化する事で傍受されても安心!という建前になっています。

暗号化された内容を解読するのはNP問題である事が分かっているので、(P≠NPという前提が守られるならば)容易に解読するP問題にはできないので安心という訳です。

という事は、逆にP=NPである事が分かってしまうとさぁ大変!暗号は頑張れば容易に解読できるP問題にできてしまう事が示されてしまったので、暗号に守られた通信の安全性は根底から崩れ去ってしまう事になります。

…と、少しオーバーに書いていますが「理論上はP=NPにできるらしい。」と分かっても、実際に目の前にあるNP問題をP問題に置き換える上手い方法がとてつもなく複雑で、実用上はとても時間がかかるという可能性も考えられます。

ある時点での暗号解読方法が分かっても、実際に解読するまでにはそれなりの時間がかかる。その間に暗号化方法を変えてしまえば良いのだ…という事です。



最後に夢のある内容を記載しておきましょう。このP≠NP予想は賞金付きの問題で、賞金は約1億円!です。

賞金をゲットするには、次のうちのどちらかを実現すればOKです。
(1)P=NPとなる具体例を1個挙げる。
(2)あらゆる問題についてP≠NPである事を証明する。

さらなるウルトラCとして、現在のコンピュータが苦戦するNP問題であろうとも一瞬で解決してしまう未来のコンピュータ、量子コンピュータを開発してしまう事です。量子コンピュータを発明できれば世界一の大金持ちになれるかもしれません。

量子コンピュータについて、別記事を作成しました】。
スポンサーサイト

テーマ : 今日のつぶやき。 - ジャンル : 日記

コメント
コメントの投稿
管理者にだけ表示を許可する