###
はじめに
有名な数学の予想が証明されると大きなニュースになります。フェルマーの最終定理は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には特別な意味がありますが、いまはただの記号だと思って差し支えありません。
この続きは以下をご覧ください
リンク
御社のプレスリリース・イベント情報を登録するには、ZDNet Japan企業情報センターサービスへのお申し込みをいただく必要がございます。詳しくは以下のページをご覧ください。