OpenAI and Anthropic claim AI proofs disproved the Exponential Time Hypothesis
OpenAI and Anthropic say their models have refuted the Exponential Time Hypothesis, a core assumption in computational complexity. Researchers have not yet independently verified the proofs, and many are assessing what it means for their own work.
1 / 2
The story, neutrally told
Mixed · 2OpenAI released solutions to three major math problems, one of which was a refutation of the Exponential Time Hypothesis (ETH), an assumption central to how computer scientists understand which problems are hard to compute. TechCrunchN “One was a surprise rejection of the Exponential Time Hypothesis (ETH), a durable assumption in computer science that plays a large role in how we understand what is difficult to compute.” Read at TechCrunch ↗ WiredLC “Both OpenAI and Anthropic claimed this week to have disproved the exponential time hypothesis (ETH).” Read at Wired ↗ Centre · 1Anthropic released its own refutation of ETH hours later, after Anthropic mathematician Levent Alpöge suggested OpenAI had built its solutions on pre-existing work, according to TechCrunch. TechCrunchN “Anthropic mathematician Levent Alpöge suggested that OpenAI was basing its solutions from pre-existing work, and hours later, Anthropic subsequently released its own refutation of ETH.” Read at TechCrunch ↗ Centre · 1The labs say their models found algorithms that solve a class of hard logic puzzles in sub-exponential time. TechCrunch notes that if this holds up it could open a path toward algorithms that bear on P versus NP. TechCrunchN “The claims from OpenAI and Anthropic is that their models have come up with algorithms that solve those puzzles in “sub-exponential” time” Read at TechCrunch ↗
Left · 1Researchers have not independently verified, or had time to fully understand, the proofs. Both firms published them on GitHub in natural language and in the machine-checkable Lean format, Wired reports. WiredLC “Researchers haven’t independently verified, let alone had time to fully understand, the AI-produced proofs, which both firms have published on GitHub in both natural language and its machine-checkable Lean format.” Read at Wired ↗ Centre · 1MIT professor Ryan Williams is organising the computer-science response. He agreed to work with the labs despite having earlier called OpenAI's October proof dump a “DDOS attack on mathematicians”. Working with him are Russell Impagliazzo and Ramamohan Paturi, who first published ETH in 1999, according to TechCrunch. TechCrunchN “Williams, whose work focuses on these questions of computational complexity, has criticized OpenAI’s approach in the past, calling its proof dump earlier this October a “DDOS attack on mathematicians.””“along with UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published the ETH in 1999.” Read at TechCrunch ↗ Mixed · 2Their first step was an open letter and a feedback form seeking input from scientists and discussion of norms for AI contributions. OpenAI has committed to fund a conference on the topic. TechCrunchN “Their first step was to release an open letter calling for feedback from scientists interested in these problems and a discussion of the norms around AI contributions to their work.” Read at TechCrunch ↗ WiredLC “So far, this effort includes a Google form asking for volunteers and feedback, and a commitment from OpenAI to fund a conference on the topic.” Read at Wired ↗
Centre · 1Williams said parts of OpenAI's proof are routine but two or three look “alien”. He said computer scientists should put somewhat more weight on P = NP being plausible, and that he doubts OpenAI's algorithm is the best possible. TechCrunchN “there are two or three alien-looking parts”“I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get.” Read at TechCrunch ↗ Left · 1Many papers assume ETH. Researcher Daniel Lokshtanov estimates that, if the result is confirmed, around 50 of his papers become “pointless” or need revisiting. Thore Husfeldt said that “as far as I can tell, it’s now all irrelevant” for his recent work, and Linköping's Jonsson expects many conference talks to begin with “ETH is false, half of my paper does not work”. WiredLC “make around 50 of his published papers either “pointless” or in need of a revisit.”““As far as I can tell, it’s now all irrelevant,” he tells WIRED.”““People will start the talks: ‘ETH is false, half of my paper does not work,’”” Read at Wired ↗ Left · 1Reactions mix dismay and excitement. Husfeldt called the finding “fantastic” and likened it to floodlights illuminating a dark room, while also describing demoralised colleagues whose projects AI results have “annihilated”. WiredLC “It's like somebody just illuminated an entire subfield in floodlights of knowledge, and now we just run around like overexcited bunnies”“the results announced by AI just annihilate the ongoing research projects of many people” Read at Wired ↗
Mixed · 2On cryptography, Williams said he asked OpenAI science lead Dan Roberts whether any systems were now insecure, and OpenAI was reasonably confident the result implies no breaks. Lokshtanov said it does not directly affect cryptography but “should definitely scare some cryptosystem designers”. TechCrunchN “they were reasonably confident that this didn’t … imply any breaks.” Read at TechCrunch ↗ WiredLC “it should definitely scare some cryptosystem designers” Read at Wired ↗ Left · 1The release follows criticism of OpenAI's earlier dump of 722 manuscripts on 400 problems, which some mathematicians saw as a hasty rollout tied to the company's planned IPO. Academics told Wired the new 60-odd-page ETH paper is better written. WiredLC “it dumped 722 manuscripts on 400 problems on GitHub, to the annoyance of academics”“This time around, OpenAI’s 60-odd-page paper on ETH seems to be written better than the companies’ past publications, academics tell WIRED.” Read at Wired ↗
Every sentence links to the reporting it rests on. The pill in front of each says where its sources sit: Left, Centre or Right when one side supplies at least half of them, Mixed when they are evenly split. The number is how many outlets it cites.
Left1 outlet
- Framing
- Human-impact story about researchers whose work is upended, with the headline calling decades of research 'irrelevant'.
- Emphasis
- Researchers' emotional reactions, wasted work, AI-generated slop, and criticism of OpenAI's earlier release and IPO motive.
- Leaves out or plays down
- Less explanation of what ETH and P vs NP mean; does not name Williams or mention the Anthropic-OpenAI priority question.
- Charged language
- “Irrelevant”“overexcited bunnies”“obliterating whole research programs”“slop-level results”“juice the company’s planned initial public offering”
Centre1 outlet
- Framing
- Explainer built around an interview with MIT's Ryan Williams, setting out what ETH, P vs NP and the claim mean and how the field is organising.
- Emphasis
- Technical context, the labs' process for sharing the proofs, and cryptographic safety.
- Leaves out or plays down
- Gives little of the distress among researchers or the criticism of OpenAI's mass proof release beyond Williams's earlier remark.
- Charged language
- “mind-bending discovery”“alien-looking parts”
- For example
-
“TechCrunch spoke to the MIT computer scientist charged with explaining OpenAI's latest mind-bending discovery” — TechCrunch
“As with previous proof-drops from the frontier lab, scientific communities responded with a mixture of thrill and dismay.” — TechCrunch
Right0 outlets
No right outlet in our sources has covered this story yet.
What every side reports
- OpenAI and Anthropic both claim to have refuted the Exponential Time Hypothesis.
- The proofs have not been independently verified.
- OpenAI has agreed to fund a conference, and researchers have opened a feedback process.
- Many existing papers rely on ETH and may need revisiting.
- Researchers expect no direct cryptographic break from the result.
Where accounts differ
-
Where the researchers who first proposed ETH are based
- Left
- Wired says OpenAI asked the UC Santa Barbara computer scientists who originally proposed the hypothesis to help.
- Centre
- TechCrunch says Russell Impagliazzo and Ramamohan Paturi, who first published ETH in 1999, are at UC San Diego.
-
Quality and motive of OpenAI's release approach
- Left
- Wired reports academic complaints about error-containing documents and a rollout seen as designed to boost an IPO, though the new paper is better written.
- Centre
- TechCrunch says OpenAI's process is evolving, with a different release structure for each discipline.
OpenAI organisation
Says its model refuted ETH, released the proofs publicly, asked researchers to help interpret them and is funding a conference; reportedly checked that no cryptosystems are broken.
“the computer scientists formed a working group, asked for the proofs to be shared publicly and OpenAI to fund a conference to discuss them” — TechCrunch
“a commitment from OpenAI to fund a conference on the topic” — Wired
Anthropic organisation
Released its own refutation of ETH hours after OpenAI's announcement.
“hours later, Anthropic subsequently released its own refutation of ETH.” — TechCrunch
Exponential Time Hypothesis topic
A long-standing assumption that hard logic puzzles need exponential time, now contested by AI-generated sub-exponential algorithms pending verification.
“It basically says that even the fastest computer algorithm needs exponentially more time to find a solution as the number of variables grow” — TechCrunch
Left1 article
-
WiredLC ·
An AI Breakthrough Has Made Decades of Computer Science Research ‘Irrelevant’
Mixed Researcher-centred account of upheaval and excitement over AI results overturning existing work, with scepticism toward OpenAI's release practices.
Centre1 article
-
Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
Neutral Explanatory interview-driven piece that unpacks ETH and P vs NP and how the community is organising.
Right0 articles
No coverage yet.
- 27 Oct 17:08 First TechCrunchN Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
- 29 Oct 10:45 +41h 37m WiredLC An AI Breakthrough Has Made Decades of Computer Science Research ‘Irrelevant’
Times are when each article was published, or when we first saw it if the outlet gave no time.
Ask about this story
Loading…