How an AI-Generated Algorithm Challenged the Exponential Time Hypothesis

This episode of the Code Report examines the exponential time hypothesis (ETH), a 1999 conjecture that has underpinned theoretical computer science for decades, and the recently published research that appears to refute it. It breaks down the background, the new result, and how researchers responded.

■ ETH の背景
- 3-SAT の仕組みと NP 完全問題であること
- 1999 年に提唱された ETH と、800 篇超の論文が依存してきた下限の役割
- 影響を受ける代表例（クリーク探索、巡回セールス問題）

■ AI が提示した新結果
- 3-SAT を解く新しい亜指数時間アルゴリズムと ETH への意味
- 解の数え上げと 19 世紀の数学を組み合わせたアプローチ
- 実際にブルートフォースを上回る規模についての言及

■ 研究者の反応と検証
- 複雑性理論研究者のコメントと P = NP に関する確率の更新
- 元の仮説の提唱者による証明の検証

■ サンスポンサー紹介
- Warp Factories の機能とベンチマークによるモデル比較

複雑性理論や AI による数学研究に関心のある方に向いており、単一の研究成果がなぜ注目されるのかの文脈を理解できます。最後にはスポンサー製品の早期アクセス案内も含まれます。