OpenAI says its AI disproved the Exponential Time Hypothesis; computer scientists will check the proof

OpenAI says its models have produced three "major" results in mathematics, computer science and physics, including a claimed proof that the Exponential Time Hypothesis is false, The Verge reported on Monday. The material has been posted to GitHub. None of it has yet been peer reviewed, and the claims should be treated as claims until experts have checked them.

The three results

Why the computer science claim is so big

The Exponential Time Hypothesis, put forward by Impagliazzo and Paturi in 1999, says that some problems, such as 3-SAT (deciding whether a set of logical conditions can all be true at once), cannot be solved much faster than by checking an exponential number of possibilities. A great deal of theoretical computer science is built on it as an assumption. If it is false, many "this cannot be done quickly" results would need rethinking. It would not, on its own, break internet encryption or settle the famous P versus NP question.

That two of the scientists who proposed the hypothesis are now leading the review is significant: they are the people best placed to find a flaw.

A new way of releasing results

This is OpenAI's second big release in a month, after it put out hundreds of manuscripts on 6 October claiming solutions to open maths problems. This time it says outside experts asked to see the computer science and physics work first. A panel of maths advisers, AGMAI, said the day before that AI companies should not give selected researchers early access, citing unequal access and borrowed reputation.

For students in Pakistan

Theoretical computer science is taught at FAST, NUST, LUMS and COMSATS, and results like this are exactly what final-year and MS students can follow as they are checked in public. Working out a CGPA for an MS application? Try our CGPA calculator.