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