Claimed math advance challenges computing hypothesis

A claimed AI-generated mathematical advance could challenge the Exponential Time Hypothesis, a longstanding conjecture about how computational difficulty grows. The proposed result concerns 3-SAT, a family of problems for which the AI reportedly found a method requiring substantially less work than the hypothesis would allow. The claim remains unconfirmed pending expert review.

If validated, the result could force researchers to revisit conclusions in hundreds of papers that assumed the hypothesis was true. It would not settle P versus NP, the question of whether every problem whose solution is easy to check is also easy to solve. OpenAI president Greg Brockman said P still probably does not equal NP, while MIT’s Ryan Williams suggested the possibility deserves greater weight. OpenAI’s science lead reportedly said the company checked that the result does not break existing encryption.

The mathematical work was reportedly checked step by step using Lean, a proof-checking program. Review is being led by UC San Diego researchers Russell Impagliazzo and Ramamohan Paturi, who proposed the hypothesis in 1999, alongside Williams. Their assessment will determine whether the claimed advance holds up.