OpenAIは27日、計算理論の長年の仮説として知られる「指数時間仮説（ETH）」に関わる3-SAT向けの新たな決定論的アルゴリズムを論文で公表した。もっとも、現時点では数学界による独立検証が続いており、実際の計算性能の改善に結び付くかどうかは今後の研究を待つ必要がある。

ブロックチェーン系メディアのDecryptによると、OpenAIが公表した67ページの論文は、3-SAT問題を従来の想定より高速に扱える可能性があるアルゴリズムを示したものだ。ETHは、「特定の問題を指数時間より大幅に速く解くアルゴリズムは存在しない」とする趣旨の仮説で、1999年の提起以降、グラフ理論や計算生物学など幅広い分野で重要な前提として参照されてきた。

今回話題となったETHは暗号資産のEthereumを指すものではない。ただ、略称がEthereumのティッカーシンボル「ETH」と同じため、暗号資産コミュニティでは混同も広がった。X（旧Twitter）では、「アルゴリズムトレーダーがイーサリアムを壊した」といった投稿や、ヴィタリック・ブテリンに絡めた冗談も見られた。

論文の焦点は、3-SAT問題における計数（解の個数を数える）アルゴリズムにある。3-SATは、複数の論理条件を同時に満たす変数の組み合わせを見つける古典的な計算問題として知られる。

OpenAIによれば、今回示した手法は、変数数に対する通常の指数関数よりも遅い増加で計算できる準指数時間の計数手法だという。結果が成立すれば、関連する計算問題の見方に影響を与える可能性があるとしている。

同社によると、AIモデルは10月16日にこの結果を見いだし、翌17日には数学的証明を機械的に検証するソフトウェア「Lean」で証明を形式化した。成果物はGitHubでも公開している。

一方、数学界は慎重な姿勢を崩していない。ラッセル・インパリアッツォ、ラマモハン・パトゥリ、マサチューセッツ工科大学（MIT）のライアン・ウィリアムズは公開書簡で、検討への参加は主張の正しさを認めることを意味しないとした上で、独立した再現と追加検証が必要だと表明した。

競合するAnthropicも26日、Claude名義で3-SAT関連アルゴリズムの論文を公開した。ただ、同社はこれについて、理論上の時間計算量の改善に関するものであり、実際の問題解決性能に直結するものではないと説明している。

OpenAIもまた、理論的な前進を実用上の性能向上に結び付けるには相当の追加研究が必要だとしている。今回の結果は、すべてのNP問題を高速に解けることを意味するものではなく、代表的な難問であるP対NP問題も未解決のままだ。

今回の研究は、AIが数学的発見に関与し得る可能性を示した一方で、その意義を確定するには第三者による独立検証が欠かせないことも改めて浮き彫りにした。