＼当サイトではリンク広告を利用しています。／
こんにちは！
いよいよ今回は、最新の「解決済み」問題に迫っていきます！
取り上げるのは、スメイルの第17番目の問題、題して……
💡「多項式を平均多項式時間で解くとは？」問題！
いきなり名前からして謎が多めですよね。
「多項式を解くって何？」「平均多項式時間ってどういうこと？」と疑問が渦巻きますが、大丈夫！この記事では、その意味や背景、誰がどのように解決したのか、ていねいにご紹介していきますよ♪
まずは問題に現れる用語を見ていきましょう。
まず、「多項式を解く」とは、与えられた多項式方程式の解（つまり根）を見つけることです。
たとえば：
f(x)=x^3+2x^2−5x+1=0
のような方程式に対して、複素数の範囲で「解 x」を見つけたいわけですね。
ですが、一般に次数が高くなればなるほど、この「解を求める」のが難しくなります。
そのため、数値的に解を「近似」する方法（数値解法）が必要になるのです。
「多項式時間」というのは、入力のサイズに対して実行時間が多項式で収まる計算を意味します。
例：サイズが NNN の入力なら、時間が N2N^2N2 や N3N^3N3 などで済むアルゴリズムのこと。
ここで「平均多項式時間」と言っているのは、「最悪のケースでは長くかかるかもしれないけど、平均的には速く解けるアルゴリズムが欲しい！」という話です。
つまり：
🌀 すべてのケースで速い必要はないけど、ほとんどのケースで速くあってほしい！
という、ある意味現実的な視点ですね。
この問題の解決には、なんと20年以上の歳月がかかりました。
2008年、カルロス・ベルトラン（Carlos Beltrán）とルイス・ミゲル・パルド（Luis Miguel Pardo）によって、
スメイルの第17問題に対する大きな進展がありました。
彼らは「平均ラスベガスアルゴリズム」という確率的手法を使って、
任意の多項式を平均的に多項式時間で解く方法を提示したのです！
ラスベガスアルゴリズムとは、正しい答えは必ず出るが、実行時間が確率的に変動するタイプのアルゴリズムです。
とはいえ、これでは「確実に速い」とは言えないため、
次は「決定論的（確実に動く）アルゴリズム」を目指す戦いが始まります。
ローレンツアトラクタの特性、ポアンカレ予想に続いて、この問題も最終的に解決をむかえます。
2016年、ついに完全な解決が登場！
このお二人が、ベルトラン・パルドのアルゴリズムを「スムージング解析（smoothed analysis）」という新しい視点で分析し、
その実行時間が「平均的に多項式時間で収まる」ことを理論的に裏付けました。
さらに、ピエール・レレーズ（Pierre Lairez）が、これを非ランダム化（＝決定論化）して、
決定論的な平均多項式時間アルゴリズムを発見！
これにより、スメイルの第17番目の問題は「平均的には、多項式時間で多項式を解ける！」という形で、晴れて解決されたのです👏
この問題が解決されたことで、数値代数幾何学・複素解析・計算理論などの分野がさらに接続され、以下のような意義が生まれました：
そしてなにより、「現実的に役に立つ数値的アルゴリズム」の構築に道を開いた、という点で応用的にも価値が大きい成果となりました。
いよいよラストスパート！
次回は「スメイルの第18番目の問題：人間と人工知能の知能の限界」をご紹介します！
最後まで解説するまで帰れま18、ついに完結間近…お楽しみに〜✨