OpenAI has announced results that call into question a long-standing hypothesis in theoretical computer science: the Exponential Time Hypothesis (ETH). It posits that certain problems become so difficult as the size of the input grows that solving them within a reasonable time using algorithms substantially faster than exponential-time algorithms is virtually impossible.

Shortly after OpenAI's announcement, Anthropic presented its own research, which also challenges ETH. If both companies' results are confirmed, this could renew the search for more efficient algorithms for problems that have been considered extremely difficult for decades.

The announcements sparked lively debate among computer scientists, mathematicians, and artificial intelligence researchers. However, verification of OpenAI's results is still underway, and the involvement of independent researchers in reviewing them does not mean they have already confirmed the company's conclusions.

Ryan Williams: a reason to take P = NP more seriously

Ryan Williams, a professor of electrical engineering and computer science at the Massachusetts Institute of Technology, is one of three independent algorithm specialists examining OpenAI's claims. He emphasized that he has not yet confirmed the company's results.

According to Williams, if OpenAI's conclusions prove correct, computer scientists will have to take the possibility that P = NP at least a little more seriously. This problem is one of the major open questions in theoretical computer science: it asks whether solutions can be found efficiently for problems whose proposed solutions can be verified in polynomial time.

Williams also noted that faster algorithms could be a practical consequence of the discovery. He had previously said that he does not believe ETH is true.

Gary Marcus: this could be a major development

Gary Marcus, a professor emeritus at New York University and a prominent critic of overly optimistic assessments of AI capabilities, responded cautiously to OpenAI's announcement.

In a post on X, he described the result as potentially significant—if it is confirmed. Marcus thus acknowledged the announcement's possible importance without declaring it proven.

John Cook: the P = NP question remains open

Mathematician and applied mathematics consultant John Cook stressed that even impressive results from OpenAI do not amount to solving one of computer science's central problems.

“The status of P = NP is still unknown,” he wrote on his blog.

Cook explained that even if exponential time can be shown to be unnecessary for the 3-SAT problem, this does not imply the existence of a polynomial-time algorithm. To the best of researchers' knowledge, no such algorithm has yet been found.

In other words, disproving ETH does not in itself prove that P = NP: these are different claims, and a substantial gap remains between them.

Joshua Fonseca Rivera: we may have underestimated computers' capabilities

Anthropic AI safety researcher Joshua Fonseca Rivera saw the announcement as a reminder that people may underestimate computational systems.

In his view, “The Bitter Lesson”—the idea that, over the long term, methods that leverage large-scale computation often outperform approaches based on manually encoded human knowledge—should have prepared researchers for discoveries like this.

“I understand this logically, but… wow, we really don't know anything,” Rivera wrote on X.

Timothy Gowers: “It is very surprising and significant that this is false”

Mathematician and Fields Medal winner Timothy Gowers, who holds a professorship at the Collège de France, briefly commented on the developments on X.

“It is very surprising and significant that this is false,” he wrote, referring to the Exponential Time Hypothesis.

Dan Shipper wishes he had studied advanced mathematics

Dan Shipper, head of the technology startup Every, reacted to the news with self-deprecating humor. He wrote that he regretted not getting a PhD in advanced mathematics.

“Not that I was ever seriously going to get one, but still,” Shipper added.

What happens next

For now, OpenAI's and Anthropic's claims should be treated as research results requiring careful independent verification, rather than a definitive resolution of a long-standing debate. OpenAI has initiated an open review of its findings by a group of external specialists, but the participants themselves emphasize that their involvement does not constitute an endorsement of the claimed results.

If ETH does turn out to be false, it could change our understanding of how efficiently certain computational problems can be solved. But this does not mean that all difficult problems will suddenly become easy, or that the P = NP question has already been settled.

The main question now is whether the results can be independently confirmed and precisely what new algorithmic possibilities they open up.