【数学】Ｐ≠ＮＰ予想、巡回セールスマン問題を通して考える「解ける」と「解けない」

まちゃひこです。最近、屁がくさいです。

科学解説シリーズ第２弾は「Ｐ≠ＮＰ予想」についてです。

この問題はミレニアム懸賞問題とよばれる、クレイ数学研究所が2000年に発表した数学の重要問題７題で、解けたら100万ドルもらえるっていう超難問のひとつとして数えられています。ちなみにミレニアム懸賞問題は

ヤン―ミルズ方程式と質量ギャップ問題

リーマン予想

Ｐ≠ＮＰ予想　←今日はココ！

ナビエ・ストークス方程式の解の存在

ホッジ予想

ポアンカレ予想

バーチ・スウィンナートン＝ダイアー予想

上記のうち、２、６は比較的よく聞くひとも多いかもしれません。６のポアンカレ予想はすでに解かれていることが有名です。

ここではミレニアム懸賞問題それぞれの問題はどういうものか、その歴史とか、そういうことは置いといて、Ｐ≠ＮＰ予想について感覚的な理解を得ることを意図しています。

※上図は先日ぼくがTwitterで公開し、１つもふぁぼもＲＴもつかなかった画像

１．Ｐ≠ＮＰ予想とは？

Ｐ≠ＮＰ予想はざっくり説明すると、コンピュータの計算はどこまで素早く解を出せるのか？　という問いに答える問題です。しかしこの記述だけではまだまだ語弊があるので、どういうことかを理解するため、少しずつ準備をしていきます。ちょっとだけ、おつきあいください。

世の中には、可能なパターンをすべて洗いざらい計算すれば必ず目的の答えが得られる、けれども現実的な時間でそれを実現するのは難しい…そのような類の問題があります。そのもっとも有名な例が「巡回セールスマン問題（Traveling saleman Problem = TSP）」と呼ばれる問題です。

上図：巡回セールスマン問題　

※引用元　http://www.s-im.t.kyoto-u.ac.jp/ja/information/laboratory/or_amp

それはアメリカ４８州を最短経路で回るためにはどういう道順が最短なのか？という問題です。この問題をコンピュータを使った計算で解くことは難しいことではありません。すべてのパターンを検証して、そのなかから最短のものを選べばいいだけなので。しかし、この問題をこのやり方でやるといったい、どれだけの時間がかかるのでしょうか？

計算するパターンは最初の出発地点固定したとして、

47×46×45×・・・×3×2×1

だけの数があります。これだけではイメージわかない感ありますが、よくいわれるのは、宇宙の年齢の１兆倍の10兆倍とか、それだけの時間がかかるというのがよくある試算です。これじゃあとても人間の我々の時間感覚では「解ける」なんていえそうにありません。

この問題から提示されるのは、「解けるとはなにか」という問いになったりします。

そこで問題を分類するってことをやるわけです。

Ｐってなに？　ＮＰってなに？

このＰとかＮＰとかいうものが、その問題タイプにあたるわけです。

それぞれ、こういう意味を付けられています。

Ｐ：多項式時間（polynomial time）

NP：非決定的多項式時間（nondeterminal polynomial time）

意味わかりませんよね。これだけじゃ。

ためしに、

「ある系に含まれるn個のデータを用いて、ある数Ｘを最小にする」

みたいな問題Ａを考えてみることにします。

数学者はこの問題Ａを特にあたって、「なにか効率的な方法（＝アルゴリズム）がある」問題をＰと呼ぶことにしました。じゃあ効率的ってなにかって話になるのですが、これは「対象となるデータ数nの多項式によって計算ステップ数を表現できる」ことをいいます。多項式、というのは

${ a_0+a_1n+a_2n^2+a_3n^3+ }$ ・・・

というものをいいます（nのべき乗の和で示せる、ということ）。計算コストはだいたいnの何乗のオーダーになっているか、というところで考えたりしますが、基本的にnの階乗とか、指数関数とか、そういうものよりもはるかに小さな数字になります。

そのため、計算ステップ数をnの多項式で書けるとかなりうれしい。なので、Ｐ（多項式時間）問題は効率的なアルゴリズムによって解ける問題、というふうに解釈されます。つまり工夫したらサクッととける、みたいな感じです。

一方で、ＮＰとはなんでしょうか？

先ほどの問題Ａに戻ってみましょう。

どうやら、今の人間の知力では問題Ａをバチッととけるアルゴリズムを見つけられない（あるかもしれないし、ないかもしれない）。

その場合はもう可能なパターンを地道に検証していくしかないかもしれません。

そういうときあるパターンiにおいて、そのときのＸの値はどうなのかチェックするとします。巡回セールスマン問題でルートを決めたうえで移動距離を計算する、みたいなことです。これはすごく簡単にサクッとできますよね。こういう、

「答えを与えられたとき、その真偽を効率的なアルゴリズムで検証可能な問題」

をＮＰといいます。

さて、ここでもう一度「Ｐ≠ＮＰ予想」とは何かを考えてみます。

この問題は名前の通り、ＰとＮＰがどういう関係にあるのか、ということを問う問題となっています。けっこうある間違いが「Ｐ問題でないもの＝ＮＰ問題」というものなのですが、Ｐ≠ＮＰ予想が持っている感覚は下図のような感じです。

f:id:bibibi-sasa-1205:20150301154908p:plain

ＮＰの特殊なケースとしてＰがある、ということだとぼくは理解しているつもりです。じゃあＮＰの円とＰの円が一致すると、どういうことになるのでしょうか？

もしもＰ＝ＮＰだったら・・・

このことについては、ランス・フォートナウという科学者の書いた本で、小説みたいな感じで描かれています。

P≠NP予想とはなんだろうゴールデンチケットは見つかるか?

作者: ランス・フォートナウ
出版社/メーカー: 日本評論社
発売日: 2014/05/13
メディア: 単行本
この商品を含むブログを見る

Ｐ≠ＮＰ予想についてまあまあ知ってる、みたいなひとにはちょっと物足りない内容ですが、はじめてこの名前を聞く、というひとには結構楽しく読めるのではないかとおもいます。

この本で、Ｐ＝ＮＰの世界は「美しい世界」と呼ばれています。

もしすべてのＮＰ問題がＰ問題であれば、「ＮＰ問題を解く最適アルゴリズムを求める」というＮＰ問題さえもＰ問題となります。頭がこんがらがりそうですが、あらゆる問題が瞬時に解ける、そういう世界が来るだろうということが書かれています。

たとえば、癌にたいし投与すべき最良の薬の調合もコンピュータの演算によりきまり、あるひとの過去のネット通販履歴を参照しながら、そのひとが最も欲している物語を創作し提供することができる、ものすごい性能をもつマテリアルの開発もできる。

しかし「解けない」ことを利用して成り立っている技術があって、それは暗号です（※公開鍵暗号）。

この「解けない」はまさに「Ｐ問題でなくＮＰ問題である」ことを想定されたものなのですので、Ｐ＝ＮＰであれば前提にしている「解けない」が成り立たなくなるため、そうとうマズイことになります。お金のやり取りはもちろん、暗号によって守られているすべてのプライバシーが危険にさらされるみたいな、そういうことが起こりえるかもしれません。

あらゆる問題が容易に解けるというのも、なかなか考え物で、解けない（＝わからない）からこそ成り立っているものっていうのもあるもんですね。たとえばひとの心とか（棒読み）。

効率的に巡回セールスマン問題を解く方法例

最後に、巡回セールスマン問題を短時間で解くアルゴリズムの一例として、遺伝的アルゴリズムというものを紹介します。最適値を見つけるために全パターン検証とか日が暮れるどころか宇宙が何兆回も生まれちゃうくらい時間がかかってしまうので、いいやり方を考えなくちゃならない。

そこで、遺伝学の発想を輸入したアルゴリズムがこれなわけです（下の動画参照）。サンプルを複数個用意し、ある優秀なやつらを残し、そいつらの特徴を継承させた次世代をつくっていく・・・というのを何度も繰り返すうちに、一番スゴいやつができるっていう発想の方法です。下の動画は一番すげーブランコ漕ぎを作ろうぜ！っていうやつです・

遺伝的アルゴリズムでブランコの漕ぎ方を学習させた。genetic algorithm Long - YouTube

まぁ、この動画を紹介したかっただけ感があるのですが、この方法のことをちょっと勉強したりすると、「突然変異」ってうまい具合に意味のあることなんやなーみたいにやたら感心してしまったりします。生物なんてぼくらも含めただ生きているにすぎないのですが、なんというか、こうしてみると「問題を解く」というものへの執念って、なんか本能的、あるいはそれ以前のなにかからはじまるとんでもないもののようにも思えます。

いやはや、生命という演算はすごいものです（棒読み）。

おつきあいいただき、ありがとうございました。

ご興味のある方は下の本などオススメです！