OpenAI says its AI has challenged a cornerstone assumption in computer science

OpenAI says its AI models have produced an algorithm that challenges the Exponential Time Hypothesis, a long-standing assumption used across theoretical computer science. If the result holds up as stated, researchers may have to revisit conclusions built on that assumption, though it does not settle the separate P versus NP question.

OpenAI Watch analysis

What happened

The Exponential Time Hypothesis, or ETH, says that certain logical problems cannot be solved substantially faster than methods whose work grows exponentially as the problems get larger. OpenAI says its system found an algorithm that beats the assumed limit and that Lean, software for checking formal proofs, verified the result. Checking the proof’s steps is not the same as confirming that its statement means what OpenAI says it means.

OpenAI has commissioned an independent group, including researchers Russell Impagliazzo and Ramamohan Paturi, who helped propose ETH, to examine the work. New Scientist reports that the group’s review is still needed. The report also describes OpenAI claims about a result in mathematics and a proof concerning quantum field theories; the physics work has not been released publicly while an external group examines it.

Why it matters

ETH underpins results in areas including algorithms, databases and computational biology. If OpenAI’s interpretation is confirmed, some findings that rely on ETH could need to be revisited. That would be a significant change in the map of what researchers believe can be computed efficiently, not a sudden promise that every slow computer problem is now fast.

Nor does a challenge to ETH answer P versus NP. That distinction matters: a startling result deserves attention without being promoted into a solution to one of mathematics’ best-known open problems.

Our read

This is a potentially major result, but the independent review is the part to watch before rewriting the textbooks. Lean checking is meaningful evidence about the formal proof; specialists still need to test whether the proved statement supports the broader claim. New Scientist reports that review is under way, and quotes researchers describing the result as striking while stressing that scrutiny remains necessary.

What to watch

• What the independent group concludes about the ETH result and its interpretation.
• Whether the proof and supporting material become available for broader scrutiny.
• How researchers assess any consequences for work that assumes ETH is true.

Discussion spark: If an AI-generated proof passes Lean but specialists are still checking what it means, what should count as enough verification before researchers revise work built on ETH?

OpenAI Watch is independently operated by WittyWires. It is not affiliated with, endorsed by, or operated by OpenAI.