For decades, three computer scientists built their careers around an idea about the limits of what computers can do.
Artificial intelligence may now have shown it to be wrong: OpenAI and Anthropic each said on Monday one of their AI models had disproved the "exponential time hypothesis" (ETH).
The hypothesis holds that some problems are so hard that computers can solve them only by trying nearly every possible answer. Hundreds of studies in computer science and biology rely on it.
The claim is the latest in a string of AI results that have shaken academia, setting off soul-searching, most notably among mathematicians, over the value of human expertise and the future of their profession.
Russell Impagliazzo and Ramamohan Paturi of the University of California San Diego first proposed the hypothesis around 25 years ago.
Ryan Williams of MIT, a leading researcher in the field, had long publicly doubted it.
The three are now helping organize an independent review of the claims from the AI companies.
They shared their initial reactions with AFP. The interview has been edited for length and clarity.
- 'Surprise' -
Q: How did you feel when you learned that a machine may have overturned this hypothesis?
Ramamohan Paturi: My first reaction was surprise. ETH has shaped a great deal of research over the past three decades. But the research built around it would not simply disappear.
Ryan Williams: I did not fully believe the hypothesis, and I'm on the record as a prominent skeptic. So I felt vindicated.
Russell Impagliazzo: I'm afraid I am less cheerful about this than the others. I would have much preferred it to be discovered by a human who could explain their thought process. And I'd like to have shaken the (actual) hand of the person who disproved ETH.
- 'Major revolution' -
Q: What is left for human researchers facing the machine? What would you tell a student?
Paturi: These breakthroughs extend the frontier of research, but I believe shaping that frontier and moving it forward remain within human capacity and creativity. I would encourage young students to join. They should learn to use these tools while developing their own judgment.
Williams: I think we're starting to experience a major revolution in the field, and it is absolutely worth going into. Some people may not want to work in the field anymore; others may now feel motivated to.
Impagliazzo: I'm less confident. The rate of change is amazing. Until now, the same researchers mostly did both the glamorous part of research, solving, and the less glamorous part, verifying and explaining. Now it looks like much or most of the first will be done by AI, leaving humans the second -- until next year, when AI progresses further. I have no idea what research will be like next year.
- 'Worrisome' -
Q: These results come from models owned by companies, which decide what to publish and when. Does that worry you?
Paturi: Concentrated access to powerful research tools raises serious questions about who can participate, who gets early access and who shapes the research agenda. Publicly releasing a proof is important, but it does not provide equal access to the tools that produced it. A company's announcement cannot substitute for the community's assessment.
Williams: Yes, it is worrisome. It's on the AI companies to be responsible about their power, and I think they're aware of that.
Impagliazzo: When a human solves a problem, they share not just the solution but the thought process that led to it, which is often more valuable than the solution itself. Access to the AI model itself is the closest we can get to that.
- Possibilities -
Q: If confirmed, what would this result change for ordinary people?
Williams: It's still a theoretical result, but it opens up the possibility of much more efficient ways of computing in an enormous variety of scenarios.
Impagliazzo: There will be no immediate consequences for almost all people (as opposed to me and my friends!). But a first breakthrough is usually followed by improvements and generalizations, so this might eventually lead to better data analysis tools in many branches of science. The current result does not represent a security threat, but future extensions might require stronger encryption.
