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には特別な意味がありますが、いまはただの記号だと思って差し支えありません。

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