まちゃひこです。最近、屁がくさいです。
科学解説シリーズ第2弾は「P≠NP予想」についてです。
この問題はミレニアム懸賞問題とよばれる、クレイ数学研究所が2000年に発表した数学の重要問題7題で、解けたら100万ドルもらえるっていう超難問のひとつとして数えられています。ちなみにミレニアム懸賞問題は
- ヤン―ミルズ方程式と質量ギャップ問題
- リーマン予想
- P≠NP予想 ←今日はココ!
- ナビエ・ストークス方程式の解の存在
- ホッジ予想
- ポアンカレ予想
- バーチ・スウィンナートン=ダイアー予想
上記のうち、2、6は比較的よく聞くひとも多いかもしれません。6のポアンカレ予想はすでに解かれていることが有名です。
ここではミレニアム懸賞問題それぞれの問題はどういうものか、その歴史とか、そういうことは置いといて、P≠NP予想について感覚的な理解を得ることを意図しています。
※上図は先日ぼくがTwitterで公開し、1つもふぁぼもRTもつかなかった画像
1.P≠NP予想とは?
P≠NP予想はざっくり説明すると、コンピュータの計算はどこまで素早く解を出せるのか? という問いに答える問題です。しかしこの記述だけではまだまだ語弊があるので、どういうことかを理解するため、少しずつ準備をしていきます。ちょっとだけ、おつきあいください。
世の中には、可能なパターンをすべて洗いざらい計算すれば必ず目的の答えが得られる、けれども現実的な時間でそれを実現するのは難しい…そのような類の問題があります。そのもっとも有名な例が「巡回セールスマン問題(Traveling saleman Problem = TSP)」と呼ばれる問題です。
上図:巡回セールスマン問題
※引用元 http://www.s-im.t.kyoto-u.ac.jp/ja/information/laboratory/or_amp
それはアメリカ48州を最短経路で回るためにはどういう道順が最短なのか?という問題です。この問題をコンピュータを使った計算で解くことは難しいことではありません。すべてのパターンを検証して、そのなかから最短のものを選べばいいだけなので。しかし、この問題をこのやり方でやるといったい、どれだけの時間がかかるのでしょうか?
計算するパターンは最初の出発地点固定したとして、
47×46×45×・・・×3×2×1
だけの数があります。これだけではイメージわかない感ありますが、よくいわれるのは、宇宙の年齢の1兆倍の10兆倍とか、それだけの時間がかかるというのがよくある試算です。これじゃあとても人間の我々の時間感覚では「解ける」なんていえそうにありません。
この問題から提示されるのは、「解けるとはなにか」という問いになったりします。
そこで問題を分類するってことをやるわけです。
Pってなに? NPってなに?
このPとかNPとかいうものが、その問題タイプにあたるわけです。
それぞれ、こういう意味を付けられています。
P :多項式時間(polynomial time)
NP:非決定的多項式時間(nondeterminal polynomial time)
意味わかりませんよね。これだけじゃ。
ためしに、
「ある系に含まれるn個のデータを用いて、ある数Xを最小にする」
みたいな問題Aを考えてみることにします。
数学者はこの問題Aを特にあたって、「なにか効率的な方法(=アルゴリズム)がある」問題をPと呼ぶことにしました。じゃあ効率的ってなにかって話になるのですが、これは「対象となるデータ数nの多項式によって計算ステップ数を表現できる」ことをいいます。多項式、というのは
・・・
というものをいいます(nのべき乗の和で示せる、ということ)。計算コストはだいたいnの何乗のオーダーになっているか、というところで考えたりしますが、基本的にnの階乗とか、指数関数とか、そういうものよりもはるかに小さな数字になります。
そのため、計算ステップ数をnの多項式で書けるとかなりうれしい。なので、P(多項式時間)問題は効率的なアルゴリズムによって解ける問題、というふうに解釈されます。つまり工夫したらサクッととける、みたいな感じです。
一方で、NPとはなんでしょうか?
先ほどの問題Aに戻ってみましょう。
どうやら、今の人間の知力では問題Aをバチッととけるアルゴリズムを見つけられない(あるかもしれないし、ないかもしれない)。
その場合はもう可能なパターンを地道に検証していくしかないかもしれません。
そういうときあるパターンiにおいて、そのときのXの値はどうなのかチェックするとします。巡回セールスマン問題でルートを決めたうえで移動距離を計算する、みたいなことです。これはすごく簡単にサクッとできますよね。こういう、
「答えを与えられたとき、その真偽を効率的なアルゴリズムで検証可能な問題」
をNPといいます。
さて、ここでもう一度「P≠NP予想」とは何かを考えてみます。
この問題は名前の通り、PとNPがどういう関係にあるのか、ということを問う問題となっています。けっこうある間違いが「P問題でないもの=NP問題」というものなのですが、P≠NP予想が持っている感覚は下図のような感じです。
NPの特殊なケースとしてPがある、ということだとぼくは理解しているつもりです。じゃあNPの円とPの円が一致すると、どういうことになるのでしょうか?
もしもP=NPだったら・・・
このことについては、ランス・フォートナウという科学者の書いた本で、小説みたいな感じで描かれています。

P≠NP予想とはなんだろう ゴールデンチケットは見つかるか?
- 作者: ランス・フォートナウ
- 出版社/メーカー: 日本評論社
- 発売日: 2014/05/13
- メディア: 単行本
- この商品を含むブログを見る
P≠NP予想についてまあまあ知ってる、みたいなひとにはちょっと物足りない内容ですが、はじめてこの名前を聞く、というひとには結構楽しく読めるのではないかとおもいます。
この本で、P=NPの世界は「美しい世界」と呼ばれています。
もしすべてのNP問題がP問題であれば、「NP問題を解く最適アルゴリズムを求める」というNP問題さえもP問題となります。頭がこんがらがりそうですが、あらゆる問題が瞬時に解ける、そういう世界が来るだろうということが書かれています。
たとえば、癌にたいし投与すべき最良の薬の調合もコンピュータの演算によりきまり、あるひとの過去のネット通販履歴を参照しながら、そのひとが最も欲している物語を創作し提供することができる、ものすごい性能をもつマテリアルの開発もできる。
しかし「解けない」ことを利用して成り立っている技術があって、それは暗号です(※公開鍵暗号)。
この「解けない」はまさに「P問題でなくNP問題である」ことを想定されたものなのですので、P=NPであれば前提にしている「解けない」が成り立たなくなるため、そうとうマズイことになります。お金のやり取りはもちろん、暗号によって守られているすべてのプライバシーが危険にさらされるみたいな、そういうことが起こりえるかもしれません。
あらゆる問題が容易に解けるというのも、なかなか考え物で、解けない(=わからない)からこそ成り立っているものっていうのもあるもんですね。たとえばひとの心とか(棒読み)。
効率的に巡回セールスマン問題を解く方法例
最後に、巡回セールスマン問題を短時間で解くアルゴリズムの一例として、遺伝的アルゴリズムというものを紹介します。最適値を見つけるために全パターン検証とか日が暮れるどころか宇宙が何兆回も生まれちゃうくらい時間がかかってしまうので、いいやり方を考えなくちゃならない。
そこで、遺伝学の発想を輸入したアルゴリズムがこれなわけです(下の動画参照)。サンプルを複数個用意し、ある優秀なやつらを残し、そいつらの特徴を継承させた次世代をつくっていく・・・というのを何度も繰り返すうちに、一番スゴいやつができるっていう発想の方法です。下の動画は一番すげーブランコ漕ぎを作ろうぜ!っていうやつです・
遺伝的アルゴリズムでブランコの漕ぎ方を学習させた。genetic algorithm Long - YouTube
まぁ、この動画を紹介したかっただけ感があるのですが、この方法のことをちょっと勉強したりすると、「突然変異」ってうまい具合に意味のあることなんやなーみたいにやたら感心してしまったりします。生物なんてぼくらも含めただ生きているにすぎないのですが、なんというか、こうしてみると「問題を解く」というものへの執念って、なんか本能的、あるいはそれ以前のなにかからはじまるとんでもないもののようにも思えます。
いやはや、生命という演算はすごいものです(棒読み)。
おつきあいいただき、ありがとうございました。
ご興味のある方は下の本などオススメです!
【おすすめ書籍】

不可能、不確定、不完全: 「できない」を証明する数学の力 (ハヤカワ・ノンフィクション文庫―数理を愉しむシリーズ)
- 作者: ジェイムズ・D.スタイン,熊谷玲美,田沢恭子,松井信彦
- 出版社/メーカー: 早川書房
- 発売日: 2012/11/09
- メディア: 文庫
- 購入: 1人 クリック: 15回
- この商品を含むブログ (3件) を見る