コラム

CTC教育サービス・ホーム　＞　コラム　＞　AI活用時代にPythonで見る夢　＞　第14回　P≠NP予想について考える（前編）

AI活用時代にPythonで見る夢

CTC 教育サービス

[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes

第14回　P≠NP予想について考える（前編） (辻真吾) 2020年7月

はじめに

有名な数学の予想が証明されると大きなニュースになります。フェルマーの最終定理は1995年に証明されるまで、フェルマー予想と呼ばれていました。2000年代はじめには、ポアンカレ予想がペレルマン氏によって証明され、彼が100万ドルの懸賞金を辞退したことでも大きな話題となりました。ちなみにこの100万ドルの懸賞金とは、米国クレイ数学研究所が設定した7つのミレニアム問題にかけられたものです。7つのうちの1つは解決されてしまいましたが、まだ6つ残っています。今回と次回のコラムでそのうちの1つ、P≠NP予想をご紹介します。

問題の難しさ

アルゴリズムとは、ある問題を解決するための一連の手続きです。身近なところでたとえると、料理のレシピはアルゴリズムと似ています。麻婆豆腐が食べたかったら材料を揃え、豆腐を切ったり挽肉を炒めたりする一連の手続きを経て、美味しい麻婆豆腐を完成させます。簡単なレシピもあれば、難しいレシピもあります。それはどこで決まるでしょうか？いろいろな考えがあるかも知れませんが、ここでは調理工程が長いと難しいと考えることにしましょう。

アルゴリズムも似たような感じで難しさを表現できます。厳密な説明ではありませんが、だいたいn回の計算で答えが得られる場合、そのアルゴリズムの計算量をO(n)と書きます。nは通常、問題のサイズに関係した変数です。数字がいくつか並んだ配列を考えましょう。[5, 6, 9, 0, 3]と並んでいれば、この配列のサイズはn=5ということになります。O(n)のOには特別な意味がありますが、いまはただの記号だと思って差し支えありません。

配列のソート

ソートとは、配列の要素を順番通りに並べ替えることです。ここでは昇順を考えるので、先頭が一番小さく、末尾の要素が最大になります。Pythonをはじめとした最近のプログラミング言語は、このような基本機能は内蔵しているので、関数やメソッドを呼び出すだけで配列がソートされます。ソートのアルゴリズムをまったく知らなくても配列をソートできるので便利です。ここでは少し立ち止まって、与えられた配列をソートするアルゴリズムを考えてみましょう。

配列のソートアルゴリズムにはさまざまなものが知られているので、いくつかのアルゴリズムをご存じの方もいらっしゃるかもしれません。私が1番好きなソートアルゴリズムは、ボゴソートです。これは、配列を適当にシャッフルして、その都度ソートされているか確認するというものです。アタリが出ればめでたく終了ですが、ハズレが出続けると地獄ですね。配列の長さがnのとき、このアルゴリズムの計算量は、O(n･n!)になります。すこしややこしいですが、n個の要素を順番に並べる並べ方は、順列と呼ばれn!です。！は階乗という数学記号で、その数から順に1まで掛けていきます。5!は5･4･3･2･1=120です。要素が5の配列では、120通りのうちどれかはソートされたものが含まれているということになります。ある配列が順番通りに並んでいるかは、先頭から要素を2つずつ比較していけばよいだけです。次々に大きくなっていれば良いですが、どこか1箇所でも次の要素が小さくなるならアウトです。これにかかる計算量がO(n)なので、あわせてO(n･n!)となります。

多項式時間

もう少し良いソートのアルゴリズムはないのでしょうか？選択ソートと呼ばれる実直な方法があります。与えられた長さnの配列から最小値を探して先頭に持ってきます。次に、その1つ後の要素から末尾までの間で最小値を探して、これまた先頭に持ってきます。これを繰り返せば最終的にソートされた配列が得られます。計算量を見積もってみましょう。長さnの配列を先頭から順番に走査して最小値を探すのに、O(n)かかります。それを配列の長さn回分だけ繰り返すことになるのでO(n²)となります。徐々に探す範囲がnより小さくなっていないか？と思う方もあるかもしれませんが、計算量の議論では細かいことは気にしません。一般的に選択ソートはボゴソートよりはるかに高速です。注目すべきは、計算量がn²とnの多項式になっている点です。このようなアルゴリズムを多項式時間（ polynomial time）アルゴリズムと呼びます。配列をソートするという問題には、多項式時間で解けるアルゴリズムがあることになるわけです。ちなみに、この多項式時間の英語の頭文字をとって、PやクラスPと呼ぶことがあります。

もし人類がアホで、配列をソートするという問題に対して、ボゴソートしか思いつけず、選択ソートを思いつけていなかったらどうなるでしょう。現在のような情報化社会は到来していないでしょうから、だいたい100年くらい前の生活をいまでもしていたことでしょう。では、人類はさまざまな問題に対して、多項式時間のアルゴリズムを考えつけているのでしょうか？実はそうではありません。多項式時間のアルゴリズムが見つかっていない問題が山ほどあります。このような問題はクラスNPに属します。クラスNPはすこしややこしいので、次回これを説明しP≠NP予想の本質に迫りたいと思います。

「付録」ソートのアルゴリズム

配列をソートするという問題には、選択ソートよりも速いアルゴリズムが知られています。クイックソートやマージソートなどはO(n･log(n))の計算量で実行できます。logの括弧は通常省略しますが、分かりやすいように書いてみました。logが入っていて通常イメージする多項式ではありませんが、これも多項式時間に分類されます。また、ソートに関してはこれ以上速いアルゴリズムは理論上は考えられないことも知られています。ただ、理論と実践はまた別の話です。いろいろな工夫で実際にソートにかかる時間を短くできます。PythonではTimSortという非常に優秀なアルゴリズムが使われています。

筆者書籍紹介

いちばんやさしいパイソンの本
Python スタートブック
　　――Pythonの基本をしっかりマスター

まったくのゼロからでも大丈夫

辻真吾　著
B5変形判／352ページ
定価（本体2,500円+税）
ISBN 978-4-7741-9643-5
詳しくはこちら（出版社WEBサイト）