これから学ぶ人も、資格取得を目指す人も、最適なカリキュラムを選べます。
これから学ぶ人も、資格取得を目指す人も、最適なカリキュラムを選べます。
CTC 教育サービス
[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes
前編では、ソートのアルゴリズムを例に多項式時間アルゴリズム（クラスP）とは何かを簡単に説明しました。配列をソートするためのアルゴリズムに、ボゴソート、選択ソート、マージソートなどがあり、それぞれ計算量がO(n･n!)、O(n2)、O(n･log(n))になることを紹介しました。O記号の使い方とはちょっと違うのですが、それぞれ具体的な数字を計算してみましょう。配列のサイズnを2,000としてみます。n2=4,000,000です。n･log(n)は、底を2として計算すると約21,931となって、かなり速いことがわかります。これに対して、n･n!は5,793桁の整数です。これは他の2つに比べて圧倒的に大きな数字です。つまり、多項式時間ではないアルゴリズムは、計算時間という点でまったく役に立たないことがわかります。
すこし前に話題になった『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！という動画をご存じでしょうか？お姉さんと子供が出てくるほのぼのしたアニメ動画ですが、内容は組み合わせ爆発の恐ろしさを表現したもので、なかなか見応えがあります。要素がn個の配列の並べ方は、その順列でn!通りです。これもまさしく組み合わせ爆発です。バカ正直に全部を並べ尽くしてソートされているかどうか調べていると、nが大きくなってきたときに宇宙が終わるまで答えがわからないということが起こり得ます。でも、人類は賢いので並べ尽くさなくてもよいアルゴリズムを考えつきました。それが、選択ソートやマージソートで、これらは多項式時間アルゴリズムです。それでは、どんな組み合わせ爆発にも対応できるアルゴリズムはあるのでしょうか？この疑問が実は解決されていません。これが、P≠NP予想の本質的な部分です。
頂点（ノード）と辺（エッジ）で表現される構造をグラフと呼びます。例えば電車の路線図は、駅が頂点、路線が辺のグラフと考えることができます。抽象的な概念なので、なんでもグラフで表現できます。ドラマの登場人物とその相関関係を表現した図をよく目にしますが、あれも立派なグラフです。ここでは頂点を都市、辺は都市と都市を結ぶ交通手段とします。ある2つの都市が、電車、バス、飛行機で結ばれていることもあるでしょうが、何らかの交通手段があれば、都市と都市が1本の辺で結ばれます。ここで次のような問題を考えます。ある出発点から、全ての都市を1度ずつ訪問して、出発点に帰ってくる順路はあるでしょうか？それぞれの都市を1度しか訪問できないところがポイントです。あるならYes、なければNoが答えです。このような順路はとくに、ハミルトン閉路と呼ばれていて、あるグラフにこのような順路があるかどうかを答える問題は、ハミルトン閉路問題と言われています。都市（頂点）がn個ある場合、すぐに思いつく解法は、全ての都市の並び順を調べ尽くす方法です。都市の並び順通りに、グラフ上で各都市を1度ずつ訪問できる順路があればYesとなり問題解決です。都市と都市の間に交通手段がなければ、その順路はだめなので次の順路を試します。全部ダメならNoが答えです。この解法の計算量はO(n!)です。さて、ハミルトン閉路問題には、ソートのときと同じように組み合わせ爆発を解決し、多項式時間で実行できるアルゴリズムがあるのでしょうか？実はまだこれがわかっていないのです。
ハミルトン閉路問題の面白いところは、ある順路（都市の並び）が与えられると、それがハミルトン閉路になっているかどうかは、多項式時間で確認できる点です。n個の都市を順に調べていけばいいので、手間はO(n)ということになります。確認するのは簡単なのに、探すのは大変。それでは、探すのはどれくらい大変なのでしょうか？この「どれくらい」という部分を適切に表現するために、計算機科学者がいろいろ思考を巡らせました。その結果、非決定性多項式時間Turing機械という空想上の計算機を考え、この機械では多項式時間アルゴリズムを作れる問題という分類を考えだしたのです。かなり話がややこしくなってきました。まず、非決定性多項式時間は、Nondeterministic Polynomial timeなので、この分類をクラスNPと呼びます。Turingは天才的な数学者として知られているあのチューリングです。非決定性Turing機械は架空の機械です。この機械の上で動くアルゴリズムでは、非決定的な動作が許されます。かなりおおざっぱに説明すると、あらかじめ動作をちゃんと決めておかなくても、その場に応じてイイ感じやってもらえるということです。ちなみに、普段みなさんが使っているコンピュータは、Turing機械がモデルとなっていて、非決定性ではなく決定性のアルゴリズムが動きます。
非決定性機械という架空の計算機を導入すると、ハミルトン閉路問題のような難しい問題にも、多項式時間のアルゴリズムが作れます。調べ尽くすのではない方法があるということです。もしP=NPなら、ハミルトン閉路問題にも多項式時間で解けるアルゴリズムがあるはずです。非決定性Turing機械ではなく、実際の計算機を使って問題を多項式時間で解くことができます。P≠NPであれば、これらのクラスには大きな隔たりがあり、やはりハミルトン閉路問題は簡単に解くことができないとわかります。これがどちらなのか、はっきりわかっていません。多くの専門家がP≠NPだと予想しています。まあ、それも当然です。非決定性Turing機械なんて、そんな架空のすごい機械なんだから、PとNPが同じなわけは無さそうです。しかし、これをきちんと証明することができないというわけなのです。ここで紹介したハミルトン閉路問題の他に、多くの問題がクラスNPに属することがわかっています。そのどれもが難しい問題で、いまだ多項式時間アルゴリズムが見つかっていません。限りなく黒に近いグレーなのに、黒だと断定できない。そんな状況だと言えるかもしれません。
P≠NP予想がどのようなものなのか、輪郭だけでも掴んでいただけたでしょうか？詳しく知りたい方には、ランス・フォートナウ著、水谷淳訳「P≠NP予想とはなんだろう（日本評論社）」がおすすめです。著名な計算機科学者が、一般向けにこの問題を解説していてわかりやすいです。いまこの瞬間も、世界のどこかで誰かがこの問題の解決へ向け、研究をすすめているかもしれません。ただ、20世紀最大の難問と言われながら、21世紀になり20年過ぎてまだ解決していないので相当の難問でしょう。私個人としては、宇宙人が来たら真っ先に答えを聞いて、100万ドルの懸賞金をもらいたいと思っています。今回はちょっと専門的な話になってしまいました。わかりやすく書こうと思いましたが、どうしても難しくなってしまったので、次回は気軽な話題にしようと思います。
| 筆者書籍紹介 いちばんやさしいパイソンの本 Python スタートブック ――Pythonの基本をしっかりマスター まったくのゼロからでも大丈夫 辻真吾 著 B5変形判／352ページ 定価（本体2,500円+税） ISBN 978-4-7741-9643-5 詳しくはこちら（出版社WEBサイト） |
 |
[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes
