OpenAIは、コンピュータサイエンス分野で20年以上にわたり用いられてきた重要な理論「指数時間仮説（ETH）」を反証したと発表した。

BlockBeatsのニュース、10月27日、OpenAIは先日、そのAIモデルがETHを「解読」したと発表し、このニュースはテック業界と暗号資産業界で瞬く間に大きな話題を呼んだ。ただし、ここで特に説明が必要なのは、このETHが暗号資産分野で広く知られるイーサリアム（Ethereum）ではなく、計算機科学において20年以上存在する重要な予想、指数時間仮説（Exponential Time Hypothesis、略称ETH）であるということだ。

指数時間仮説の核心的な問題は、いわゆる「特に計算が難しい」問題が、一体どれほど難しいのかということである。

一部の人が聞いたことのある「SAT問題」（ブール充足可能性問題）を例に挙げると、これは、たくさんの論理条件が与えられたとき、すべての条件を同時に成立させるような値の割り当てを見つけられるかということを問うている。問題の規模が大きくなると、現在知られている最良の方法は基本的に可能な答えを一つずつ試すしかなく、時間コストは規模に応じて指数関数的に増大する。これがよく言われる「指数時間」である。ETHはさらに、この種の問題は本質的に大幅に高速化することは不可能であり、真の意味での「準指数時間」の効率的アルゴリズムは存在しないと断言している。

この仮説は1999年に提唱されて以来、理論計算機科学の重要な基盤であり続けている。数百、数千もの論文がこれに基づいて「ある問題は難しい」「あるアルゴリズムはすでに最適に近い」ことを証明している。もしETHが覆されれば、私たちが「これ以上速くするのはほぼ不可能」と考えている多くの問題に対して、理論的にはより良い解法が存在する可能性があることを意味する。

OpenAIは今回、そのモデルが準指数時間でk-SAT問題の解の数を正確に数え上げる決定的アルゴリズムを見つけ、Leanを用いて形式検証を行ったと主張している。もしこの結果が最終的に専門家の審査に耐えうるものであれば、指数時間仮説を直接揺るがすことになる。