編集部からのお知らせ
「ZDNet Japan Summit」参加登録受付中! 
新着記事集:「負荷分散」

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

CTCテクノロジー株式会社(CTC教育サービス)

2020-10-19 09:00

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予想の本質的な部分です。

この続きは以下をご覧ください
(リンク »)
本プレスリリースは発表元企業よりご投稿いただいた情報を掲載しております。
お問い合わせにつきましては発表元企業までお願いいたします。

【企業の皆様へ】企業情報を掲載・登録するには?

御社の企業情報・プレスリリース・イベント情報・製品情報などを登録するには、企業情報センターサービスへのお申し込みをいただく必要がございます。詳しくは以下のページをご覧ください。

NEWSLETTERS

エンタープライズ・コンピューティングの最前線を配信

ZDNet Japanは、CIOとITマネージャーを対象に、ビジネス課題の解決とITを活用した新たな価値創造を支援します。
ITビジネス全般については、CNET Japanをご覧ください。

このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]