月曜日, 12月 10, 2012

P対NP問題と安全保障

どうでも良いことかもしれないけど(笑)・・・・・P対NP問題って分かりますか?35年ほど前、本気でコンピュータを勉強しようとしたときこの問題に出くわしたのを覚えています。「知の限界」かもしれないこの数学理論は未だに答えが出ていないのではないかな。昨日、ぱらぱらと雑誌をめくっていたら、最近こう言う問題がまた出て来ているんだと。もしかしたら知っている人も居るかもね。



要するに、全てのイエスノークエスチョンはコンピュータで高速に解けるのか?と言う話。Pとは現実的時間で計算して答えが出る事で、NPとは現実的時間で検証可能であるかと言う事。
分かりやすく言うと、ジグソーパズルがあって、それを計算して素早く答えを出す方法はかなり難しいのだけれど、実際出来上がったパズルは即座に正しいかどうか分かる訳ですよね。ピースの数が膨大に膨れあがったとしても、結果はすぐに検証できますが、どのピースを何処におけば良いかなんて計算は出来ません。
これをP≠NP予想と言います。でも、もしかしたらひどく簡単な方法でパズルが完成するアルゴリズム理論が出来たならP=NPな訳です。多分(笑)。

でもなぁ、4x=20なんて言う方程式はx=5とすぐに出て来ますから。計算が即時可能なPな訳です。そしてxに5を代入して20になる検証もすぐに出来ちゃう。う〜ん、と言う事はP=NPだろう、、なんて簡単にいかないところが数学。このP=NPアルゴリズムが未だ効率の悪い、ジグソーパズルのようなアルゴリズムに取って代われば良いのだけれど、未だそれは実現してはいないのですよ。まあ中には、素数判定というかつてのNP問題が、つい最近2002年にlog nの多項式を上限とする決定的多項式時間で判定できることが分かり、P=NPとなったことは、まあ、どうでも良いけど、すごいニュースだったわけですね。でもこれで素因数分解が出来るかどうかはまだ分かっていないからP≠NPと言うわけです。。。

どうですか。眠くなるでしょ(笑)。

ちなみに、ワシらが頻繁に使うGoogleではNPには触れないようにしているらしい。そりゃそうだよね。検索アルゴリズムが時間評価である以上、何分も何時間も待たせられては仕事にならない。検索の完璧さより時間でしょ。完璧か否かは自分の脳がはき出す近似値で判断しているわけでこれこそがP≠NPなわけだろうな。自分の頭の中の脳細胞ニューロンは、多分同じ事をしているに違いないしその限界を近似値からはじき出しているに違いないと思いますな。

ワシら根管治療して適否の検証はわりとすぐに出来るけど、その方法が一定の即解できるアルゴリズムに従っているかどうかと言えば答えはノーだものなぁ。だって千差万別の根管に対しての計算値は近似値でしか判定できないものなぁ。でもこう言う事が解決すれば、日本の抱える安全保障から、近所のディーラーの営業マンの成績まで、量計算できるなんて、、、、ん?素敵な世界だろうか?
個人的には、「限界」があった方が良いんじゃないかと思う。
眠くなったでしょ(笑)。どうでもいい話でした(笑)。


0 件のコメント: