OpenAI said on Monday, October 26, that its internal models produced three new results: a proof of the local smoothing conjecture in every dimension, existence proofs for QCD and pure Yang-Mills theory, and, the one that drew the most attention, a disproof of the Exponential Time Hypothesis (ETH). Our news explainer covers what OpenAI announced. This roundup covers what complexity theorists, mathematicians and developers said in the first seven hours.
The short version: experts took the ETH claim seriously and called it a big deal if it holds, while stressing that it is not yet vetted. Several pushed back on the most common misreading, that it brings P = NP or broken encryption. A SAT-solving researcher called the algorithm "galactic", meaning far from practical. The sharpest criticism was about process: who gets to see the results first, and whether $5 million to the Simons Foundation is a fair return to the research community.
Most of the discussion below comes from two Hacker News threads, one on OpenAI's announcement (633 points and 271 comments by late Monday) and one on the ETH paper itself (427 points, 163 comments), plus posts on X and Scott Aaronson's blog. Reddit was not reachable for this roundup.
What OpenAI claimed
Per OpenAI's announcement, the ETH result is a disproof found by its system and then verified in Lean, a language that checks proofs by machine. The paper and Lean formalization are public on GitHub. A group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will verify and shepherd it. The physics result is held back while a group led by David Gross writes it up.
How experts explained it
Ryan Williams, the MIT complexity theorist in the checking group, gave the plainest summary on X. "ETH claims 3SAT cannot be solved in 1.000... 01^n time for some number of zeroes. They claim ETH is false, giving an algorithm that is "sub-exponential" time for 3SAT. That would be surprisingly faster than brute force, the 2^n time," he wrote.
He added: "If true, their claim implies a variety of other NP problems now all have faster algorithms as well. Since 3SAT is NP complete, this should make every computer scientist put at least a little more weight on the possibility of P = NP."
Lance Fortnow, a complexity theorist, summed up the claim as "solving 3SAT (even counting the number of solutions) in 2^{o(n)} time, with a Lean formalization of the proof," and shared the checking group's message: "Our involvement should not be taken as certification of the claim."
Scott Aaronson, who works on complexity theory, wrote on his blog that "my students just came to my office to tell me that an OpenAI model has now refuted the Exponential Time Hypothesis, by giving an algorithm to solve 3SAT in an amount of time that scales roughly like exp(n/√log(n))." He framed it as one more result in a long run of AI math releases: "Even as we struggle to digest the previous courses, the endless buffet continues."
Lijie Chen, a UC Berkeley assistant professor who also works on reasoning at OpenAI, posted that the ETH is false, in capital letters. OpenAI scientist Dan Roberts wrote that the checking group "invites the community to help organize an open examination of the ETH claim."
Praise: a big result, if it holds
On Hacker News, the reaction from commenters who said they read or write papers that use the ETH was mostly surprise. "It's a huge result if true, and probably the first major AI result that affects the papers I read," wrote jltsiren.
CaptainNegative, who said their thesis worked with several hardness conjectures, wrote: "So grounded was ETH that I introduced it in a side note as Conjecture 0 after Conjectures 1 and 2." emil-lp guessed that "ETH has been assumed in thousands of papers. I have several myself," and saw an upside: "suddenly there's a whole bunch of open problems."
Williams expects more to come. Asked on X about 3SAT in exp(n^(0.9)) time, he replied: "I would guess the probability is at least 0.75. If OpenAI's algorithm is correct, there's absolutely no way it's the end of the story."
OpenAI's Noam Brown pointed to the pace: "Only 2.5 years ago, AI labs would highlight their frontier LLM performance on grade school math benchmarks (GSM8K). I can't wait to see where we'll be in another 2.5 years."
The math result drew its own fans. "The proof of the Kakeya conjecture is amazing. Only 54 pages. Will probably lead to a lot of theory," wrote vatsachak, who said they hold a PhD in non abelian harmonic analysis.
Pushback: not P = NP, and not broken encryption
Many early replies jumped to P = NP or cryptography. Experts pushed back. OpenAI president Greg Brockman posted: "p still probably doesn't equal np."
On Hacker News, cochne quoted the paper's own limit: "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."
Ryan O'Donnell replied on X to a question about older results built on the ETH: "No results assuming ETH fall, per se. All these results are of the form "there is a very efficient algorithm reducing 3SAT to problem X". And these algorithms continue to work correctly."
On encryption, Williams wrote: "In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result. Apparently they are safe..." In a comment on Aaronson's blog, Joshua Zelinsky checked factoring and concluded the new bound "is still worse than any L-notation bound," so it does not beat the number field sieve.
Is it practical? Not yet
"SAT-solving expert here. No immediate applications (the results in the paper are "galactic")," wrote bsubs. "The main question is whether some ideas here will snowball into other ideas, one of which could eventually be very practical."
Williams was candid about the timeline. "Honest answer: we don't know yet. At the current rate of progress, it's plausible we could see a serious update on practical SAT solving within the next 12 months. Or we might not see anything like that. I really don't know," he wrote.
He also joked about how much weight a Lean check carries. "I asked, "Are you sure?" They replied that they'd verified it in Lean. I said, "OK but are you sure?"" he posted.
O'Donnell tried a different route to understanding the proof. He said he discussed the paper with an LLM and had it write a 12-page version that "seems to do a clearer job of explaining the main ideas," with a disclaimer: "no idea if it's correct."
Complaints: access, credit and money
The process drew the most criticism. sobellian wrote: "There's a large logical leap from "we have very useful raw research data" to "we should give this data only to a small group of people.""
titzer offered a cynical "translation" of OpenAI's post: "Our results are too important to wait for the pesky peer review, so we are dumping a whole ton of money in a fund and giving some elites a breathless first look so our buzz keeps getting jacked up."
esalman looked at the $5 million Simons Foundation contribution and wrote that it "might sustain 5-10 PhD students for 5 years." sharmajai asked how much the work cost and whether an equal sum spent on human researchers would have produced the same results.
Others saw progress. "I think OpenAI deserve credit for adjusting their approach after the last math drop," wrote stillpointlab, who also credited Terence Tao for pushing the response. rao-v disagreed: "I'm not sure what meaningfully changed except for the QCD / yang mills result (where leaders in the field are going to do a review and write up first)."
The physics claim drew shrugs
The Yang-Mills and QCD result got less attention, and some doubt about how new it is. "The QCD and Yang-Mills results don't seem to go beyond what the experts know/expect," wrote auntienomen. "Basically, they're saying there is a path integral measure, but shrugging when asked what functions are integrable with respect to it."
cft asked: "Did any physicist really doubt it? 4d QCD has been used for approximate calculations for about 45 years." auntienomen added that the open question of which functions are integrable "is key for mass gap and confinement." OpenAI describes the Yang-Mills existence proof only as "part of" the Clay Millennium Prize problem.
What it means
The early expert view is consistent: the ETH claim is a major result if the checking group confirms it, it does not settle P versus NP, it does not break today's encryption, and it is not a faster SAT solver anyone can use. The open questions are about process as much as math: how fast outside researchers can check the proof, and who gets early access to results like this.
The next things to watch are the Impagliazzo, Paturi and Williams group's report, the open examination Dan Roberts described, and the physics group's write-up.
Sources
- OpenAI: Working with academic communities to build scientific understanding
- OpenAI math repository: The Exponential Time Hypothesis is False (paper)
- Hacker News: Three new discoveries in mathematics, computer science, and physics
- Hacker News: The Exponential Time Hypothesis Is False
- Scott Aaronson, Shtetl-Optimized: Podcasts about the Topic, Part II
- Ryan Williams on X
- Lance Fortnow on X
- Ryan O'Donnell on X
- Greg Brockman on X
- Noam Brown on X
- Dan Roberts on X
- llms.blog: OpenAI Says Its AI Disproved the Exponential Time Hypothesis
