OpenAIが指数時間仮説を否定する証明を発表

OpenAIは「指数時間仮説は偽である（The Exponential Time Hypothesis is False）」と題したプレプリントを発表し、Lean定理証明器で検証された形式証明を公開しました。この論文では、$n$変数上の標準的にエンコードされた $k$-CNF 式の充足割り当てを、多項式領域を使用して $(n+m)^{O_k(1)} imes 2^{O_k(n imes ext{loglog} n / ext{sqrt}( ext{log} n))}$ の時間でカウントできる決定論的アルゴリズムを提示しています。この結果は、3-SATが劣指数時間では解けないと仮定する指数時間仮説（ETH）を形式的に否定するものです。

結果の理解とその範囲

この結果は計算複雑性理論における重要な理論的ブレイクスルーですが、NP完全問題が多項式時間で解ける（P=NP）ことを意味するわけではありません。コミュニティの研究者が指摘するように、このアルゴリズムはSATに対して劣指数時間の解法を提供しますが、その実行時間は実用的なアプリケーションにとっては依然として「天文学的に遅い」ものです。

「この劣指数時間の解法は、線形個の変数で3SATに還元できるあらゆる問題に適用可能です。具体的には、独立集合のカウント、適切なq彩色数のカウント、完全マッチングのカウントなどが挙げられます。」 — @cochne

重要なのは、この劣指数時間の利点が変数($n$)の数に対して相対的であるという点です。他のNP困難問題から3-SATへの標準的な多項式時間還元では通常変数の数が増大するため、このアルゴリズムの劣指数的な性質は還元のオーバーヘッドによって相殺されてしまうことがよくあります。その結果、この成果は現時点でNP完全問題の困難性に依存する暗号システムを脅かすものではありません。

理論的含意と実証的含意

Hacker Newsでの議論では、この証明の数学的な重要性と即時的な有用性との間の隔たりが強調されました。一部の観察者は、アルゴリズムの定数や劣指数的な高速化が現れるために必要な入力の膨大なサイズを考慮すると、これは純粋に理論的なものに過ぎないと指摘しました。

「$n = 1{,}000$ 変数の場合、指数はすでに $\sim 1{,}000 \times 5 / 5 \approx 1{,}000$、つまり $2^{1000}$ となり、実行可能な計算をはるかに超えています。」 — @jaekwon

現在のハードウェアに対する実用的な影響はないものの、この結果は、NP完全問題には固有の指数関数的な下限が存在するという、多くの複雑性理論家が長年抱いてきた直感に挑戦するものです。Leanによる形式化は証明の正しさに対する高い信頼性を提供し、議論を従来の紙とペンによる検証の枠を超えたものにしています。

数学的発見におけるAIの役割

今回の発表は、幾何学から量子複雑性まで幅広いトピックを網羅する、OpenAIの数学部門による一連のプレプリントの一部です。自動化ツールを使用してこのような複雑な証明を生成・検証する能力は、数学研究の未来に関する議論を巻き起こしています。

「LLMが数学に強いのは、このレベルの数学には誤りがほとんどないからではないかと思います。コードには常にバグがつきものですが……数学では証明が存在するかしないかのどちらかであり、Leanのようなツールを使えば常に自動的に検証可能です。」 — @martin-t

AIが生成した証明の「ブラックボックス」的な性質について懐疑的な意見を持つユーザーもいますが、Leanによる検証への依存は、人間の直感だけでなく、機械によってチェックされた証明の妥当性が受け入れの主要な基準となるパラダイムへの移行を示唆しています。