Refutation of the Exponential Time Hypothesis
OpenAI says its models found sub-exponential algorithms for a hard class of logic puzzles, which would refute the Exponential Time Hypothesis. Anthropic claimed its own refutation hours later.
OpenAI released solutions to three math and science problems, one of which rejects the Exponential Time Hypothesis, a long-held assumption about how hard some computing problems are. The claimed algorithms solve a tricky class of logic puzzles in sub-exponential time. MIT's Ryan Williams, with Russell Impagliazzo and Ramamohan Paturi, is organizing the computer science community's review, and OpenAI was asked to share the proofs publicly and fund a conference.
- Date
- Tuesday 27 October 2026
- Lab
- OpenAI
- Kind
- paper
- Access
- paper only
The claim is not yet verified by the community. Williams said OpenAI checked and was reasonably confident no cryptographic systems are broken.
Sources
- techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-h
- theinformation.com/briefings/openai-anthropic-claim-cryptography-breakthrough-day
This record was partly confirmed: some claims could not be checked on 27 October 2026. How we check