Two artificial intelligence developers, OpenAI and Anthropic, announced on Monday that their models were able to refute the so-called exponential time hypothesis (ETH). The hypothesis was proposed about 25 years ago by Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego. It holds that some problems are so complex that a computer can solve them only by going through nearly all possible answer options. Hundreds of studies in computer science and biology have been built on this idea.
Three specialists whose careers are tied to the hypothesis - Impagliazzo, Paturi and Ryan Williams of the Massachusetts Institute of Technology (MIT), who has long publicly doubted ETH - are now helping organize an independent review of the companies' claims. They shared their first reactions with AFP.
Paturi admitted that at first he was surprised: the hypothesis has set the direction of research for three decades. But, he said, the work built around it will not disappear. Williams said he felt satisfaction, since he had been a well-known skeptic. Impagliazzo took the news with less enthusiasm: he would have preferred the discovery to be made by a human able to explain the course of their thoughts, and he would like to shake the hand of the person who refuted the hypothesis.
Asked what remains for human researchers, Paturi said breakthroughs expand the boundaries of science, but defining those boundaries and pushing them further is the task of human creativity. He advised students to master AI tools while developing their own judgment. Williams believes a major revolution is beginning in the field and that it is worth joining. Impagliazzo is less certain: previously the same scientists both solved problems and checked solutions, but now a significant part of the first task appears likely to be performed by AI, leaving the second to humans.
The scientists are also concerned that the results were obtained by models owned by companies that themselves decide what and when to publish. Paturi noted that concentrating access to powerful research tools raises questions about who can participate in science and influence its agenda. Publishing a proof is important, but it does not provide equal access to the tools that produced it. Williams called the situation alarming and added that responsibility for using their power lies with the companies. Impagliazzo recalled that a person solving a problem shares not only the answer but also the course of thought, which is often more valuable than the solution itself.
If the result is confirmed, there will be no immediate consequences for most people, according to Impagliazzo. However, a first breakthrough is usually followed by improvements and generalizations, so over time this could lead to more advanced data analysis tools in various fields of science. Williams added that for now this is a theoretical result, but it opens the possibility of far more efficient computing in many scenarios. Impagliazzo also noted that the current result does not create a security threat, but future extensions may require more robust encryption.