# Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?

DevFeed: [Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](<https://devfeed.tech/articles/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean-102422.md>)

Original publisher: [Read original article](<https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/>)

Author: Tim Fernholz

Published: 2026-10-27T17:08:08Z

Content type: news

Language: en

Sources: [TechCrunch | AI News & Artificial Intelligence](<https://devfeed.tech/sources/techcrunch-ai-news-artificial-intelligence.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Frontier AI](<https://devfeed.tech/topics/frontier-ai.md>), [ai security](<https://devfeed.tech/topics/ai-security.md>)

Tags: [ai](<https://devfeed.tech/tags/ai.md>), [ai-labs](<https://devfeed.tech/tags/ai-labs.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [anthropic](<https://devfeed.tech/tags/anthropic.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [conference](<https://devfeed.tech/tags/conference.md>), [crypto](<https://devfeed.tech/tags/crypto.md>), [cryptographic](<https://devfeed.tech/tags/cryptographic.md>), [cybersecurity](<https://devfeed.tech/tags/cybersecurity.md>), [discovery](<https://devfeed.tech/tags/discovery.md>), [eth](<https://devfeed.tech/tags/eth.md>), [exclusive](<https://devfeed.tech/tags/exclusive.md>), [exponential-time-hypothesis](<https://devfeed.tech/tags/exponential-time-hypothesis.md>), [frontier-ai](<https://devfeed.tech/tags/frontier-ai.md>), [mit](<https://devfeed.tech/tags/mit.md>), [models](<https://devfeed.tech/tags/models.md>), [openai](<https://devfeed.tech/tags/openai.md>), [techcrunch](<https://devfeed.tech/tags/techcrunch.md>)

## AI overview

OpenAI and Anthropic say their models found algorithms that solve a class of hard logic puzzles in sub-exponential time, potentially refuting the Exponential Time Hypothesis (ETH), which holds that such problems require exponentially more time as their variables grow. MIT computer scientist Ryan Williams says the proofs contain a few unusual parts that merit scrutiny, and that a valid refutation could challenge assumptions behind many research papers and raise the plausibility of P = NP. He also says OpenAI reported checking whether the result affects cryptographic systems and was reasonably confident it implied no breaks. To assess the work and its implications, computer scientists have formed a working group, issued an open call for feedback, and asked OpenAI to fund a conference. Williams cautions that the result may not be the final or best possible algorithm.

## Source excerpt

TechCrunch spoke to the MIT computer scientist charged with explaining OpenAI's latest mind-bending discovery