ETHは偽である——OpenAIの証明を簡略化した論文が公開される
A simplified proof of ETH is False [pdf]
計算複雑性理論の核心的な仮説ETH（指数時間仮説）を否定する論文。任意の固定ε>0に対し、3-SATを2のεn乗のオーダーで解く決定的アルゴリズムが存在すると主張する。OpenAIの証明を、スパース化・出現回数の制限・スペクトル置換・有理補間という4つの要素に整理し、初等的な線形代数と多項式補間だけで再構成。ETHが成り立つならP≠NPの議論にも影響が及ぶ。
我々は、変数を小さなグループに分割でき、各節が1つのグループだけを使うなら、グループごとに充足割り当てを数えて掛け合わせればよい。困難なのは、節が異なるグループを結びつけることだ。我々はこの結びつきを代数的に取り除く。