--- title: OpenAI's internal model claims a disproof of the... description: An internal OpenAI model has produced a claimed disproof of the Exponential Time Hypothesis, a conjecture that hundreds of computer science papers rely on.... canonical: https://daily.dev/posts/openai-s-internal-model-claims-a-disproof-of-the-exponential-time-hypothesis-xrd0xvwjn twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: OpenAI's internal model claims a disproof of the Exponential Time Hypothesis | daily.dev og:description: An internal OpenAI model has produced a claimed disproof of the Exponential Time Hypothesis, a conjecture that hundreds of computer science papers rely on.... og:url: https://daily.dev/posts/openai-s-internal-model-claims-a-disproof-of-the-exponential-time-hypothesis-xrd0xvwjn og:image: https://api.daily.dev/og/posts/Xrd0XVWjN.png og:image:alt: OpenAI's internal model claims a disproof of the Exponential Time Hypothesis og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # OpenAI's internal model claims a disproof of the Exponential Time Hypothesis **[Collections](https://daily.dev/sources/collections)** · 2 min read · 4 upvotes · 0 comments ## Summary An internal OpenAI model has produced a claimed disproof of the Exponential Time Hypothesis, a conjecture that hundreds of computer science papers rely on. OpenAI says the model found the disproof on October 16, and the proof was checked in Lean the next day. Verification is led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego, who proposed ETH about 25 years ago, along with Ryan Williams of MIT. They stress their involvement isn't an endorsement. OpenAI also announced AI-produced results on the local smoothing conjecture and a proof that pure Yang-Mills theory exists, and gave $5 million to the Simons Foundation for related workshops. ## Content OpenAI says one of its internal models has disproved the Exponential Time Hypothesis (ETH), the conjecture that 3SAT needs exponential time. The hypothesis has held for about 25 years, and hundreds of computer science papers on problem hardness rest on it. According to OpenAI, the model found the disproof on 16 October and the proof was checked in Lean the next day. A PDF titled "The Exponential Time Hypothesis is False" has been posted in the openai/math repository on GitHub. ## Who is checking it OpenAI has asked outside researchers to verify and explain the work. The group is Russell Impagliazzo and Ramamohan Paturi of UC San Diego, who helped formulate ETH, and Ryan Williams of MIT. They say their involvement is not an endorsement. @rrwilliams posted that they have been asked to assess the claimed refutation. There's a nice irony here: the people who proposed the hypothesis are now the ones testing whether it falls. Mathematician @wtgowers, in a post relayed by @charliermarsh, called the result very surprising and consequential if it holds. ## What it would and wouldn't mean Disproving ETH would not settle P versus NP. By itself, it would not establish a change in practical quantum advantage either. It would change what researchers can assume about how hard certain logic problems are, and papers that depend on ETH would need a second look. ## The other announcements OpenAI made several other claims the same day: - Mathematics: a proof of the local smoothing conjecture, a 35-year-old problem about how waves focus, which would also settle the Kakeya conjecture. Humans had only solved smaller versions. - Physics: proofs that quantum field theories, including quantum chromodynamics and pure Yang-Mills theory, exist with full mathematical rigor. OpenAI says the Yang-Mills result covers half of the $1 million Yang-Mills Existence and Mass Gap Millennium Prize problem. A separate team led by David Gross will examine the quantum field theory claims. OpenAI also gave $5 million to the Simons Foundation for related workshops. All of this is still a claim awaiting independent review. A Lean check is a strong sign for the ETH proof, but the experts' verdict is what will decide it. ## Questions this post answers ### What is the Exponential Time Hypothesis and why does it matter in computer science? The Exponential Time Hypothesis (ETH) is a conjecture about how hard certain computational problems are, and hundreds of computer science papers rely on it when arguing about problem hardness. It was proposed about 25 years ago by Russell Impagliazzo and Ramamohan Paturi, who are now involved in checking a claimed disproof of their own conjecture. _Follow how this verification unfolds on daily.dev before citing ETH-based hardness results in your own work._ ### Did an OpenAI model actually disprove the Exponential Time Hypothesis? OpenAI claims an internal model produced a disproof of ETH on October 16, with the proof checked in Lean the next day. However, the claim is still unconfirmed: Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams are reviewing it, explicitly stating their involvement is not an endorsement, so the result remains a claim pending expert review. _Track the expert review of this claim on daily.dev before treating it as settled complexity theory._ ### What other AI-produced math and physics proofs has OpenAI announced alongside the ETH claim? On the same day as the ETH disproof claim, OpenAI announced AI-produced results including progress on the local smoothing conjecture in mathematics and a proof that pure Yang-Mills theory exists in physics. OpenAI also donated $5 million to the Simons Foundation to fund related workshops. _Keep up with AI-generated research claims across math and physics via daily.dev as verification efforts continue._ ## Community take How the wider developer community reacted, aggregated from 1 discussion and 129 comments across hackernews (as of 2026-10-27). **TL;DR:** Commenters are genuinely excited about a claimed proof that 3SAT (and thus ETH) is solvable in subexponential time, but a long technical sub-thread repeatedly clarifies that this does NOT show all NP problems are subexponential or move P vs NP much, because polynomial-time reductions to 3SAT can blow up problem size enough to erase the gain. **Sentiment:** 35% positive · 55% mixed · 10% skeptical **The case for** - Several see it as a genuinely rare and significant complexity-class separation (NP != EXP) if it holds up. - It's framed as evidence that worst-case hardness for NP-complete problems may be less extreme than assumed. - One commenter notes a quoted expert slightly raising their personal probability estimate for P=NP. **The pushback** - Multiple commenters stress the result does not imply NP is subexponential, since poly-time reductions to 3SAT can reintroduce exponential blowup. - Some call the practical impact 'galactic' — i.e. theoretically interesting but useless for real-world SAT solving. - A few questioned whether the paper is needlessly hard to read/verify and whether it could even be AI-generated output passed through with little human vetting. - One thread disputes an incorrect claim that ETH relates to self-attention/Transformer complexity bounds, showing confusion about implications for LLM hardware costs. **By community** - hackernews (mixed): Initial excitement about the claimed proof quickly gives way to an extended, technical back-and-forth correcting overreaching claims about what the result actually implies for P vs NP and practical algorithms. **Hottest debate:** Whether the subexponential 3SAT algorithm implies anything about NP problems in general, given that polynomial-time reductions to 3SAT may negate the subexponential speedup. **Open questions** - Does this technique generalize to other NP-complete problems despite the reduction blow-up issue? - What is the next 'natural' lower bound candidate for NP-complete problem complexity if ETH is false? - Will the proof hold up under full verification, and is the paper's length/style evidence of AI-assisted generation? - Are there any practical SAT-solving applications beyond the theoretical ('galactic') algorithm described? **Highlights** > If they had instead found that it were true, it'd prove P!=NP (since 3SAT is in NP and proving ETH would imply it can't be solved in polytime) Instead we now know that NP is a strict subset of EXP (there are problems in NP that can be solved in subexponential time). And in fact they provided a constructive proof that 3SAT (and thus any problem in NP) can be solved in subexponential (but still super-quasipolynomial, let alone polynomial) time. Edit: Originally wrote the hypothesis being true would imply NP=EXPTIME, which is wrong, since there can be problems in EXPTIME which aren't in NP. > — [krackers on hackernews · 2 comments](https://news.ycombinator.com/item?id=50252446) > See this from the paper: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems admit subexponential time algorithms." > — [cochne on hackernews · 2 comments](https://news.ycombinator.com/item?id=50252736) > SAT-solving expert here. No immediate applications (the results in the paper are "galactic"). The main question is whether some ideas here will snowball into other ideas, one of which could eventually be very practical. > — [bsubs on hackernews · 3 comments](https://news.ycombinator.com/item?id=50253117) > Scott Aaronson comments on his blog "Given this news, I’ll up my personal probability of P=NP from 3% to 5%." (https://scottaaronson.blog/?p=10239#comment-2042428) > — [mudita on hackernews · 1 comments](https://news.ycombinator.com/item?id=50252719) > the language around complexity domains is really confusing. P means "this problem can be solved in polynomial # of steps relative to the problem size" NP means "we don't know if the problem can be solved in polynomial # of steps relative to problem size, but we know we can check if the result is correct in a polynomial # of steps relative to the problem size" Prior to today, it was widely suspected that there are problems in NP where it requires an exponential # of steps relative to problem size. We now know that any problem in NP requires AT MOST something more than polynomial but strictly less than exponential to solve. "P = NP" means "if you can check it in polynomial time, there's some way to solve it in polynomial time". "P != NP" means "there are some problems checkable in polynomial time for which there is no polynomial way to obtain the result" Today's new proof makes "P = NP" "feel more likely", because we know there can't be algorithms requiring exponential # of steps if it's checkable in polynomial time. There still might be algorithms that require superpolynomial, but sub-exponential # of steps. It was widely suspected that a set of problems called "NP-complete" ("the hardest problems in NP") might take exponential number of steps. They do not. > — [dnautics on hackernews · 1 comments](https://news.ycombinator.com/item?id=50253153) **Source threads** - [hackernews](https://news.ycombinator.com/item?id=50251661) · 289 points · 129 comments ## Similar posts on daily.dev - [Human mathematicians are being outcounterexampled](https://daily.dev/posts/human-mathematicians-are-being-outcounterexampled-ocacgpf22) · Hacker News · 3 upvotes · 0 comments --- Tags: [#openai](https://daily.dev/tags/openai) [View this post on daily.dev](https://daily.dev/posts/openai-s-internal-model-claims-a-disproof-of-the-exponential-time-hypothesis-xrd0xvwjn) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"OpenAI's internal model claims a disproof of the Exponential Time Hypothesis","url":"https://daily.dev/posts/openai-s-internal-model-claims-a-disproof-of-the-exponential-time-hypothesis-xrd0xvwjn","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/openai-s-internal-model-claims-a-disproof-of-the-exponential-time-hypothesis-xrd0xvwjn"},"datePublished":"2026-10-26T22:52:59.006Z","dateModified":"2026-10-27T14:55:11.108Z","description":"An internal OpenAI model has produced a claimed disproof of the Exponential Time Hypothesis, a conjecture that hundreds of computer science papers rely on....","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/f87d130ae0b4d944b79aebec015e1de7?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/f87d130ae0b4d944b79aebec015e1de7?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Collections","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Collections","logo":"https://media.daily.dev/image/upload/s--fk_6ycEi--/f_auto,q_auto/v1780996001/logos/collections?_a=BAMAMiWQ0","url":"https://daily.dev/sources/collections"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/openai-s-internal-model-claims-a-disproof-of-the-exponential-time-hypothesis-xrd0xvwjn","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":4},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"openai","timeRequired":"PT2M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Collections","item":"https://daily.dev/sources/collections"},{"@type":"ListItem","position":3,"name":"OpenAI's internal model claims a disproof of the Exponential Time Hypothesis"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/openai-s-internal-model-claims-a-disproof-of-the-exponential-time-hypothesis-xrd0xvwjn#faq","mainEntity":[{"@type":"Question","name":"What is the Exponential Time Hypothesis and why does it matter in computer science?","acceptedAnswer":{"@type":"Answer","text":"The Exponential Time Hypothesis (ETH) is a conjecture about how hard certain computational problems are, and hundreds of computer science papers rely on it when arguing about problem hardness. It was proposed about 25 years ago by Russell Impagliazzo and Ramamohan Paturi, who are now involved in checking a claimed disproof of their own conjecture. Follow how this verification unfolds on daily.dev before citing ETH-based hardness results in your own work."}},{"@type":"Question","name":"Did an OpenAI model actually disprove the Exponential Time Hypothesis?","acceptedAnswer":{"@type":"Answer","text":"OpenAI claims an internal model produced a disproof of ETH on October 16, with the proof checked in Lean the next day. However, the claim is still unconfirmed: Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams are reviewing it, explicitly stating their involvement is not an endorsement, so the result remains a claim pending expert review. Track the expert review of this claim on daily.dev before treating it as settled complexity theory."}},{"@type":"Question","name":"What other AI-produced math and physics proofs has OpenAI announced alongside the ETH claim?","acceptedAnswer":{"@type":"Answer","text":"On the same day as the ETH disproof claim, OpenAI announced AI-produced results including progress on the local smoothing conjecture in mathematics and a proof that pure Yang-Mills theory exists in physics. OpenAI also donated $5 million to the Simons Foundation to fund related workshops. Keep up with AI-generated research claims across math and physics via daily.dev as verification efforts continue."}}]} ```