AI活用時代にPythonで見る夢　＞　第15回　P≠NP予想について考える（後編）

私が編集支援しているCTC教育サービスのコラム「AI活用時代にPythonで見る夢　＞　第15回　P≠NP予想について考える（後編）」が公開されました。

＃＃＃

前回のおさらい
前編では、ソートのアルゴリズムを例に多項式時間アルゴリズム（クラス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予想の本質的な部分です。

この続きは以下をご覧ください
https://www.school.ctc-g.co.jp/python/columns/tsuji/tsuji15.html