k-sat

OpenAI は最近、同社の AI モデルがコンピュータサイエンスにおいて20年以上続いている推測指数時間仮説、英語の略称 ETH を解明したと発表しましたが、これはイーサリアムではありません。この仮説は、特に計算が難しい問題がどれほど難しいかに焦点を当てており、ブール充足可能性問題 SAT を例に挙げています：与えられた論理条件のセットに対して、すべての条件が同時に成立するような割り当てが存在するかどうか。問題の規模が大きくなると、既知の最良の方法は基本的に可能な解を一つずつ試すしかなく、時間のコストは規模に対して指数的に増加します。指数時間仮説はさらに、この種の問題は本質的に大幅に加速できず、真の意味での亜指数時間効率的なアルゴリズムは存在しないと主張しています。この仮説は1999年に提唱されて以来、理論計算機科学の重要な基盤となっており、多くの論文がそれに基づいて特定の問題が非常に難しいことや、特定のアルゴリズムが最適に近いことを証明しています。もし指数時間仮説が覆されると、ほとんど不可能と考えられている多くの問題に対して、理論的にはより良い解法が存在するかもしれません。OpenAI は、そのモデルが k-SAT 問題の解の数を亜指数時間内で正確に統計する決定論的アルゴリズムを見つけ、Lean を用いて形式的に検証したと主張しています。この結果が最終的に専門家の審査に耐えられるなら、指数時間仮説を直接揺るがすことになります。