OpenAI、新しいアルゴリズムで指数時間仮説を反証したと主張

ChainCatcherの情報によると、OpenAIは先日、コンピュータ科学において20年以上にわたり受け入れられてきた「指数時間仮説」（英語略称：ETH）をAIモデルが解決したと発表しました。これはイーサリアムとは無関係です。この仮説は、特に計算が困難な問題がどれほど難しいかを扱っており、ブール満足可能性問題（SAT）を例に挙げています：与えられた論理条件の集合に対して、すべての条件を同時に満たす割り当てが存在するかという問題です。問題の規模が大きくなると、既知の最良の方法はほぼすべての可能性を一つずつ試すことであり、計算時間は規模に対して指数的に増加します。指数時間仮説は、このような問題は本質的に大幅な高速化が不可能であり、真に亜指数時間で効率的なアルゴリズムは存在しないと主張しています。この仮説は1999年に提唱されて以来、理論計算機科学の重要な基盤となっており、多数の論文がこれを前提として、特定の問題が困難であることや特定のアルゴリズムがほぼ最適であることを証明してきました。もし指数時間仮説が否定された場合、これまでほぼ不可能だと考えられてきた問題について、理論的にはより良い解法が存在する可能性があります。OpenAIは、自社のモデルがk-SAT問題の解の数を亜指数時間で正確に数え上げる決定的アルゴリズムを発見し、Leanを用いて形式的検証を行ったと主張しています。もしこの結果が専門家の審査を最終的に通過すれば、指数時間仮説そのものが直接揺らぐことになります。