OpenAIが「指数時間仮説は偽」とする論文を公開

The Exponential Time Hypothesis Is False [pdf]

OpenAIのGitHubリポジトリ「math」に、計算複雑性理論の根幹をなす指数時間仮説（ETH）を否定する論文が公開された。ETHはP≠NPより強い仮定として知られ、SATの求解に要する時間の下限を定めるもの。これが偽となれば、アルゴリズム研究の前提が大きく揺らぐ。同リポジトリには他にも多数の数学的成果が並ぶ。