OpenAIは、指数時間仮説(Exponential Time Hypothesis)は誤りだと題した数学論文を公開しました。証明が正しければ、現代の理論計算機科学の作業前提の一つ、つまりある標準的な種類の最も難しい論理パズルは、すべての可能性を試すよりも大幅に速くは解けないという前提が崩れます。公表済みの困難性に関する結果の多くがこの仮説に依拠しているため、反証が確認されれば分野全体で見直しが必要になります。
論文は2026年10月17日付で、10月25日に改訂されました。GitHub上のOpenAIの公開数学リポジトリに置かれ、著者は個人名ではなくOpenAIとだけ記されています。リポジトリによれば、収録された原稿は名前の明かされていないOpenAIの社内モデルが作成したもので、完成した論文ではなく生の研究データとして扱うべきだとされています。60ページを超える本論文の主定理は、2以上の任意の固定されたkについて、k-CNF式(高々k個の項からなる節で構成される論理式)を満たす割り当てをすべて数える決定的アルゴリズムを示します。実行時間はおおよそ2のn/√(log n)乗で増え(nは変数の数)、メモリ使用量は多項式のままです。これは多項式時間より遅いものの、定数×nを指数とするどの2のべき乗よりも速く、まさに仮説が否定する速さです。解を数えることは解の有無を判定するより難しいため、この結果は仮説の数え上げ版も反証し、論文の主張では、より強い関連仮説も反証することになります。
手法は代数的です。序論を読む限り、変数をグループに分け、式を低次の多項式方程式に置き換え、補間と高速な総和によってそれらの共通零点を数えるもので、以前のsplit-and-list法や包除原理の手法を土台にしています。論文は帰結として、グラフ彩色、独立集合、完全マッチングの部分指数時間での厳密な数え上げや、Max-k-SATの近似手法を挙げています。一方で、この形の時間上界は通常の帰着では引き継がれないため、すべてのNP問題に高速なアルゴリズムが得られるわけではないと慎重に断っています。
背景を考えると慎重さが欠かせません。3-SATに対するこれまでの最良の厳密計数アルゴリズムは明らかに指数時間のままで、PPSZアルゴリズムとその改良を含む数十年の研究でも、指数の底はゆっくりとしか下がってきませんでした。また論文の系の一つは、9月に出た別のOpenAIのプレプリントThe Unique Games Theoremに依拠しており、こちらも査読を経ていません。
いずれも査読を受けておらず、OpenAI自身のリポジトリも、Leanによる形式的証明のない結果には誤りが含まれうると注意しています。計算量理論の専門家による公表された反応も、私たちはまだ目にしていません。この規模の結果は過去にも発表されては撤回されてきており、専門家がすべての補題を検討して初めて穴が見つかることが多くありました。今とるべき姿勢は、関心を持ちつつも信じ込まないことです。論文は専門家が一歩ずつ検証できるほど詳細に書かれており、どんな論評よりも先に、その判定が決着をつけるでしょう。