Copernicus AI Podcast podcast

The Exponential Time Hypothesis is false?

0:00
8:28
Rewind 15 seconds
Fast Forward 15 seconds
Two AI companies, OpenAI and Anthropic, each released a paper claiming that the Exponential Time Hypothesis, a central working assumption of computer science, is false. We explain what the hypothesis says, why so much rested on it, what would change if it has fallen, and how far to trust two company releases that have not been peer reviewed. Disclosure: this episode was edited with help from Claude, an AI model made by Anthropic, one of the two companies discussed. ## References ### Peer-reviewed papers - Impagliazzo and Paturi (2001). On the Complexity of k-SAT. Journal of Computer and System Sciences. DOI: 10.1006/jcss.2000.1727 (peer reviewed) (abstract supplied by the producer) (https://doi.org/10.1006/jcss.2000.1727) - Impagliazzo et al. (2001). Which Problems Have Strongly Exponential Complexity?. Journal of Computer and System Sciences. DOI: 10.1006/jcss.2001.1774 (peer reviewed) (abstract supplied by the producer) (https://doi.org/10.1006/jcss.2001.1774) ### Company releases (not peer reviewed) - OpenAI (2026). The Exponential Time Hypothesis is False. family 378, commit 4eaee8754. [company release, not peer reviewed; status: Lean formalization listed in OpenAI's catalogue, catalogue review status unchecked] - Anthropic (2026). A 2^ Time Algorithm for 3-SAT. https://raw.githubusercontent.com/anthropics/formal-math/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth/paper.pdf (fetched 2026-11-03, sha256 7af518b09342). [company release, not peer reviewed; status: unverified] ### Commentary and reporting - Ryan O'Donnell, personal page, Carnegie Mellon (30 October 2026). Some exposition of "The Exponential Time Hypothesis Is False". [commentary: reported, not a source for any claim that a result is true] https://www.cs.cmu.edu/~odonnell/some_eth_false_exposition.pdf - Lance Fortnow, Computational Complexity blog (28 October 2026). The Exponential Time Refutation. [commentary: reported, not a source for any claim that a result is true] https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html - Wikipedia (3 November 2026). Exponential time hypothesis. [commentary: reported, not a source for any claim that a result is true] https://en.wikipedia.org/wiki/Exponential_time_hypothesis - Mary McCue Bell, The Washington Times (27 October 2026). Did AI just solve a 30-year-old computer science puzzle? Experts are checking. [commentary: reported, not a source for any claim that a result is true] https://www.washingtontimes.com/news/2026/oct/27/openai-says-model-refuted-exponential-time-hypothesis/ ## Hashtags #CopernicusAI #SciencePodcast #ResearchInsights #ComputerScience #TechResearch

More episodes from "Copernicus AI Podcast"