OpenAI 新论文声称指数时间假设（ETH）不成立
OpenAI 发布新论文，声称给出一个确定性亚指数时间算法，可精确计数 k-SAT 的解，若证明成立将推翻指数时间假设（ETH）。论文直白地以《The Exponential Time Hypothesis Is False》为题，ETH 是现代细粒度复杂度理论的核心假设之一，长期被用于论证大量问题家族可能无法被实质性加速求解。若该证明成立，建立在 ETH 和 SETH 之上的大量条件性下界将需要重新检验。论文还声称这一结果对 #SAT、图着色、独立集、完美匹配等问题也有影响。
OpenAI 声称的亚指数算法若获证明成立，基于 ETH 和 SETH 的大量条件性下界将需要重新检验。
The Exponential Time Hypothesis Is False!
OpenAI just shook one of the foundations of computer science.
In a new paper bluntly titled “The Exponential Time Hypothesis Is False,” OpenAI claims a deterministic, subexponential-time algorithm for exactly counting solutions to k-SAT — which would refute ETH, one of the central assumptions underpinning modern fine-grained complexity theory.
ETH has long been used to argue that huge families of problems probably cannot be solved substantially faster. If this proof holds, a large body of conditional lower bounds built on ETH and SETH will need to be re-examined.
The paper also claims consequences for #SAT, graph coloring, independent sets, perfect matchings, and more.