{"id":"openai-math/The-Exponential-Time-Hypothesis-is-False","pdf":"https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026","score":1,"title":"The Exponential Time Hypothesis is False","domain":"Theoretical computer science","family":"378","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"OpenAI's October 25 manuscript claims deterministic exact #k-SAT in subexponential time and polynomial space, refuting ETH for k=3. The published Lean scope states an exponent O_k(n (log log n)^2 / sqrt(log n)); the manuscript gives sharper bounds with one log log n and a further sparse-input improvement. Those sharper bounds are not claimed here as Lean-verified. Released October 26 for independent examination.","category":"research","comments":2,"disputed":false,"division":"cs","mentions":0,"discussed":19,"published":"2026-10-25","reactions":{"up":1},"discussion":[{"url":"https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html#:~:text=In%20this%20week%27s%20big%20news","kind":"web","site":"blog.computationalcomplexity.org","text":"In this week's big news (though it's only Wednesday), OpenAI announced a proof that the exponential-time hypothesis is false , with a Lean proof . Later Anthropic released their own paper . Ryan O'Donnell and Shiva Kintali posted follow-up proofs, smartly focusing on simplicity rather than getting…","added":"2026-11-03","title":"The Exponential Time Refutation","author":"Lance Fortnow"},{"url":"https://blog.computationalcomplexity.org/2026/11/3sum-and-apsp-and-eth-oh-my.html#:~:text=Throughout%20this%20post%20I%20will%20assume%20that%20the%20recent%20results%20by%20OpenAI%20and%20Anthropic","kind":"web","site":"blog.computationalcomplexity.org","text":"Throughout this post I will assume that the recent results by OpenAI and Anthropic contain correct proofs of what they claim.) I wrote the following about 2 years ago but did not post it. It's dated, but that's the point. BEGIN DOCUMENT FROM TWO YEARS AGO Why do we think \\(P\\ne NP\\)? a) Lots of…","added":"2026-11-03","title":"3SUM and APSP and ETH, Oh My!","author":"Bill Gasarch"},{"url":"https://www.scientificamerican.com/article/dueling-proofs-from-openai-and-anthropic-astound-scientists/","kind":"web","site":"Scientific American","text":"The results resolve major problems in math, physics and computer science. But like other recent AI-generated “slop drops,” the releases are already controversial","added":"2026-11-03","title":"Dueling proofs from OpenAI and Anthropic astound scientists","author":"Joseph Howlett, Peter Hall"},{"url":"https://www.huanqiukexue.com/?p=5001#:~:text=10%E6%9C%8826%E6%97%A5%EF%BC%8C%E5%A8%81%E5%BB%89%E5%A7%86%E6%96%AF%E5%9C%A8%E7%A4%BE%E4%BA%A4%E5%B9%B3%E5%8F%B0","kind":"web","site":"huanqiukexue.com","text":"10月26日，威廉姆斯在社交平台“蓝天”（Bluesky）上发文， 谨慎地将这项成果称为OpenAI“声称的证伪” 。他特意说明，三人没有签署保密协议，也不收取报酬，可以自由向同行分享审查进展。他们还要求OpenAI公开论文、Lean代码等原始材料，并出资支持学界举行讨论会议，OpenAI已同意他们的要求。 随后，三人在《致理论计算机科学界关于ETH的信》（ Message to the TCS Community on ETH ）中再次划清界限：…","added":"2026-11-04","title":"科学家相信了30年的假说，发过数百篇论文，可能被OpenAI证伪了 – 环球科学","author":"环球科学"},{"url":"https://x.com/rrwilliams/status/2114833319431209352","date":"2026-10-26","kind":"x","added":"2026-11-03","author":"Ryan Williams @rrwilliams.bsky.social","handle":"rrwilliams"},{"url":"https://x.com/wtgowers/status/2114846058622718221","date":"2026-10-26","kind":"x","added":"2026-11-03","author":"Timothy Gowers @wtgowers","handle":"wtgowers"},{"url":"https://x.com/BooleanAnalysis/status/2114860617924243776","date":"2026-10-26","kind":"x","added":"2026-11-03","author":"Ryan O'Donnell","handle":"BooleanAnalysis"},{"url":"https://x.com/rrwilliams/status/2114891835403633038","date":"2026-10-27","kind":"x","added":"2026-11-03","author":"Ryan Williams @rrwilliams.bsky.social","handle":"rrwilliams"},{"url":"https://x.com/fortnow/status/2114875562623635783","date":"2026-10-27","kind":"x","added":"2026-11-03","author":"Lance Fortnow","handle":"fortnow"},{"url":"https://ethdiscussion.blog/2026/10/26/eth-refutation-examination-and-discussion/","date":"2026-10-27","kind":"web","site":"ETH: Community Examination and Discussion","text":"Dear colleagues,OpenAI has informed us that it has obtained a claimed refutation of the Exponential Time Hypothesis and plans to release the supporting documents to the community. Our names may app…","added":"2026-11-03","title":"ETH Refutation: Examination and Discussion","author":"Russell Impagliazzo, Ramamohan Paturi, Ryan Williams"},{"url":"https://mathoverflow.net/a/516430","date":"2026-10-27","kind":"web","site":"mathoverflow.net","text":"The date of this result was October 25 rather than October 6, but still seems worth mentioning. The exponential time hypothesis is false . While there wasn't complete consensus, I think it's fair to say that most complexity theorists expected it to be true. The falsity of the exponential time…","added":"2026-11-04","title":"Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?","author":"Timothy Chow"},{"url":"https://cstheory.stackexchange.com/questions/57311/how-to-salvage-arguments-that-assume-eth","date":"2026-10-27","kind":"web","site":"cstheory.stackexchange.com","text":"If the recent claims that the exponential time hypothesis (ETH) is false – see here and here – turn out to hold, then a lot of recent algorithmic impossibility results are \"vacuously true\". However, the conceptual message of most papers still seems to hold, in essence: obtaining substantially…","added":"2026-11-04","title":"How to salvage arguments that assume ETH","author":"Hermann Gruber"},{"url":"https://cstheory.stackexchange.com/a/57313","date":"2026-10-27","kind":"web","site":"cstheory.stackexchange.com","text":"I think it's impossible to give a generic answer, as things depend on the specifics of each reduction. My area is parameterized complexity, so I can venture a guess about what will happen here if instead of assuming the ETH, we assume instead that \"3-SAT cannot be solved in time…","added":"2026-11-04","title":"Answer to: How to salvage arguments that assume ETH","author":"Michael Lampis"},{"url":"https://x.com/BooleanAnalysis/status/2115532387685720199","date":"2026-10-28","kind":"x","added":"2026-11-03","author":"Ryan O'Donnell","handle":"BooleanAnalysis"},{"url":"https://bsky.app/profile/joshuagrochow.bsky.social/post/3myxe5r4zg227","date":"2026-10-28","kind":"web","site":"Bluesky Social","text":"...papers that assume ETH. Many of those results can probably be \"rescued\" with minor changes (since the disproof of ETH is only by a tiny amount) - some discussion cstheory.stackexchange.com/q/57311/129 and cstheory.stackexchange.com/q/57309/129. https://cstheory.stackexchange.com/q/57311/129","added":"2026-11-03","title":"Joshua Grochow (@joshuagrochow.bsky.social)","author":"Joshua Grochow"},{"url":"https://x.com/rrwilliams/status/2115847690588442802","date":"2026-10-29","kind":"x","added":"2026-11-03","author":"Ryan Williams @rrwilliams.bsky.social","handle":"rrwilliams"},{"url":"https://x.com/BooleanAnalysis/status/2115876059673440339","date":"2026-10-29","kind":"x","added":"2026-11-03","author":"Ryan O'Donnell","handle":"BooleanAnalysis"},{"url":"https://cstheory.stackexchange.com/a/57317","date":"2026-10-30","kind":"web","site":"cstheory.stackexchange.com","text":"Michael points out above that the known proofs of the slightly superexponential bounds $2^{o(k\\log k)}$ and of the $f(k)\\,n^{o(k)}$ bound for Clique do not go through under Weak ETH. Both follow from a different weakening of ETH, the conclusion of Theorem 14.12 of Cygan et al., Parameterized…","added":"2026-11-04","title":"Answer to: How to salvage arguments that assume ETH","author":"Stefan Szeider"},{"url":"https://cstheory.stackexchange.com/a/57324","date":"2026-11-03","kind":"web","site":"cstheory.stackexchange.com","text":"Your premise is wrong. For every $\\epsilon>0$ , there is an EXP-complete problem computable in time $2^{n^\\epsilon}$ by a trivial padding argument. Thus, you will only get $\\mathsf{NP\\subsetneq EXP}$ if you show that SAT is in $\\mathsf{DTIME}(2^{n^{o(1)}})$ . The violations of ETH in the recent AI…","added":"2026-11-04","title":"Answer to: Consequences for NP versus EXPTIME if the Exponential Time Hypothesis (ETH) is false","author":"Emil Jeřábek"}],"formalized":true,"family_title":"Disproof of the Exponential Time Hypothesis","formalizations":["https://github.com/openai/math/blob/main/lean/docs/378.md"]}