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

CTC教育サービスはコラム「コラム > AI活用時代にPythonで見る夢 > 第14回 P≠NP予想について考える(前編)」を公開しました。

###

はじめに
有名な数学の予想が証明されると大きなニュースになります。フェルマーの最終定理は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には特別な意味がありますが、いまはただの記号だと思って差し支えありません。

この続きは以下をご覧ください
リンク

本プレスリリースは発表元企業よりご投稿いただいた情報を掲載しております。
お問い合わせにつきましては発表元企業までお願いいたします。

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