OpenAIは、同社のAIモデルが1999年に提唱された計算機科学の予想「指数時間仮説(ETH)」を反証する手法を見つけたと発表した。この主張は、ティッカーETHで取引される暗号資産イーサリアムや、その共同創設者であるビタリック・ブテリン氏とは無関係である。

それでもこの発表は、Crypto Twitterでジョークの的にされた。「アルゴトレーダーが$ETHを完全に屠りやがった」というユーザーTakumi氏がXに投稿し、Andrew Jiang氏は「この発表が出てから、Vitalikはすっかり静かだな」と皮肉った。

問題のETHは、計算機科学者のラッセル・インパリアッツォ氏、ラマモハン・パトゥリ氏、フランシス・ゼイン氏によって提唱された。これは、3-SATとして知られる論理問題が、変数の組み合わせをすべて調べる方法よりも本質的に速く解くことはできないと主張するものだ。3-SATでは、真偽の割り当てがルールの集合を満たすかどうかを判定することを目標とし、各ルールには3つの変数が含まれる。

OpenAIによると、数百の学術論文がこの仮説に依拠し、グラフ理論、計算生物学、データベース、幾何学における特定の問題が高速には解けないことを示してきた。同社は、ETHが反証されれば、これらの課題がどれだけ高速化されうるかという問いが再び開かれ、より優れたアルゴリズムの探索に役立つ可能性があるとしている。

「ETHの反証は、これらの課題がどれだけ高速化されうるかという問いを再び開くものだ」とOpenAIはブログ記事で述べ、「より優れたアルゴリズムの探索の指針となる可能性がある」としている。

10月17日付で10月25日に改訂されたOpenAIの全67ページの論文は、ランダム性を用いない決定論的アルゴリズムについて記述しており、これはこうしたパズルの充足割り当てをすべて準指数時間で数え上げるものだ。これは、計算量が変数の数に関するいかなる指数関数よりも緩やかに増加することを意味する。解の個数を数えることは、解が少なくとも一つ存在するかを判定するよりも難しいため、より難しい問題が解ければ判定問題も自動的に解けることになる。

OpenAIによると、同社のAIは10月16日にこの反証を発見し、10月17日に、各論理ステップを機械的に検証するソフトウェアであるLeanで形式化された。論文と形式化はGitHubで公開されている。OpenAIは、これは今月上旬に公開された722件の数学原稿の続きであり、そのうち計算機検証済みの主結果が付いたのは162件のみだったと述べている。この機械検証可能な形式こそが、独立した研究者が議論の各ステップを自ら検証することを可能にしている。

インパリアッツォ氏、パトゥリ氏、MITのライアン・ウィリアムズ教授がこの主張の独立検証を主導しており、公開書簡の中で、自身らの参加は承認と解釈されるべきではないと慎重に注意を促した。

「我々の関与は、この主張の保証と受け取られるべきではない」と3氏は書き、「これほど重要な成果には、慎重かつ独立した精査と、他の研究者が再構築し、疑問を呈し、発展させられるという理解が必要だ」と付け加えた。

OpenAIによると、参加者は秘密保持契約を結んでおらず無報酬で作業しており、同社はすべての生データの公開と、この成果に関する会議への資金提供に合意したという。

実用面での波及効果は依然として先の話だ。「そのようなアルゴリズムの発見や、理論的進展の実用面での改善への転換には、さらなる大規模な研究が必要となる」とOpenAIは述べた。論文自体も、この成果は複雑性クラスNPのすべての問題が準指数時間で解けることを示すものではないとしている。

つまり、P対NP問題は未解決のままだ。Pは計算機が効率的に解ける問題のクラスであり、NPは提案された解を効率的に検証できる問題のクラスだ。未解決の問いは、解の検証が効率的にできるすべての問題が、解くことも効率的にできるかどうかというものである。

Anthropicは10月26日、Claudeによるものとされる「A 2^o(n) Time Algorithm for 3-SAT」と題する論文でこの議論に参戦した。リポジトリも同じETH問題に取り組んでおり、社内の研究用Claudeモデルがこのアルゴリズムを発見したとしている。さらに「この結果は純粋に漸近的なものであり、実務上の公式求解には何も語らない」と付記している。

Claudeは9月にフェルマーの最終定理をLeanで形式化しており、数学者のテレンス・タオ氏はこうしたAI努力の重複の可能性を警告していた。同氏は9月に「誰かがある問題に取り組んでいるという噂だけでも、元の研究プロジェクトが本来の潜力に達する前に、それをなぎ倒そうとする膨大なAI駆動の努力を引き起こしうることが、我々はすでに目の当たりにした」と記している。

OpenAIのシモンズ財団への最近の500万ドルの寄付は、研究者がAIによる成果を検証し、発展させることを支援するワークショップ、会議、特別プログラムの資金となる。

出典:Decrypt