OpenAIのフロンティアAIが、数学・計算機科学・物理学の「3大難問」を解決か？

新アルゴリズムによる27年来の「計算時間の壁」を突破

　今回OpenAIが発表したのが、理論計算機科学の根幹を支えてきた「指数時間仮説（Exponential Time Hypothesis：ETH）」を覆すとする成果だ。ETHは1999年に提唱された仮説で、特定の複雑な論理問題については、どれほど効率的な計算方法を開発しても、計算時間が指数関数的に増大することを根本的には避けられないと考える、いわば「計算時間の壁」についての仮説だ。例えば、100個のスイッチをONかOFFに切り替え、特定の条件を満たす組み合わせを探す場合、可能な組み合わせは2の100乗、約126穣通りにも達する。


　こうした問題の代表例が「3-SAT」と呼ばれる論理充足可能性問題である。ETHは、3-SATを解く計算時間を入力規模に対してサブ指数時間にまで短縮することは不可能だと予想してきた。この仮説はグラフ理論、データベース、計算生物学など、多くの研究で計算困難性を示す理論的な前提として利用されている。

　OpenAIが発表した新しいアルゴリズムは、従来の総当たりとは異なる方法で問題を解く。まず複雑な論理条件を数学的な式に変換し、膨大な変数を小さなグループに分割する。さらに変数同士の依存関係を整理し、計算しやすい状態を作り出す。その上で、調整用のパラメータを導入し、多項式補間などの数学的手法を利用して、簡単な状態で得られた情報から本来の問題の答えを復元する。 例えるなら、巨大な迷路の経路を一つずつ調べる代わりに、迷路を複数の区画に分解し、それぞれの構造を解析して出口までの経路を組み立てるような仕組みだ。


　これにより、計算時間を従来の指数時間よりも増加の遅い「サブ指数時間」に抑えられることを示したという。ただし、これは「P対NP問題」が解決したことを意味せず、既存の暗号システムが直ちに破られるわけでもない。最大の衝撃は、長年、計算の限界を示す根拠とされてきたETHそのものが成立しない可能性が示されたことだ。OpenAIは10月16日にAIが証明を生成し、翌17日に数学証明支援システム「Lean」で形式化したと説明している。ETHの提唱者であるラッセル・インパリアッツォ氏らが独立検証を進めている。