OpenAI announced that one of its internal models produced a proof which, if confirmed, refutes the Exponential Time Hypothesis (ETH), a core assumption in theoretical computer science about how hard problems such as 3-SAT are to solve. The company published the proof and a formal check in the Lean language on GitHub. Researchers including Ryan Williams, Russell Impagliazzo and Ramamohan Paturi are organising an independent review, which is not an endorsement. OpenAI also presented results on other maths problems and a new way of working with academics.

What it means: If the result survives scrutiny, it would be one of the most significant in complexity theory for years, and it would have come from an AI system. Until then, caution is the right stance: the Lean check confirms that the steps are logically sound, but experts still need to confirm that the formal statement really matches the hypothesis everyone has in mind. For businesses the immediate practical impact is small. A subexponential algorithm does not automatically mean fast programs, and it does not threaten today’s cryptography, which rests on different problems. The more interesting message lies elsewhere: models are starting to produce original research that machines can check. That matters to any software team thinking of using AI for optimisation, for example in shift planning, routing or rule checking, where formal verification is becoming more accessible. Greek technology firms should keep an eye on tools such as Lean and formal proof methods, because combining them with AI could sharply cut errors in critical code such as payments and tax integrations.

Read the original on The Verge

Related service: Custom software

Related stories