{"id":749960,"date":"2026-10-27T20:55:22","date_gmt":"2026-10-27T17:55:22","guid":{"rendered":"https:\/\/buradabiliyorum.com\/en\/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean\/"},"modified":"2026-10-27T20:55:22","modified_gmt":"2026-10-27T17:55:22","slug":"frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean","status":"publish","type":"post","link":"https:\/\/buradabiliyorum.com\/en\/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean\/","title":{"rendered":"Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_89 counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-6aedcbb0519f3\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #dd3333;color:#dd3333\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #dd3333;color:#dd3333\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-6aedcbb0519f3\" checked aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/buradabiliyorum.com\/en\/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean\/#Are_you_down_with_P_vs_NP\" >Are you down with P vs NP?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/buradabiliyorum.com\/en\/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean\/#The_work_ahead_for_computer_scientists\" >The work ahead for computer scientists<\/a><\/li><\/ul><\/nav><\/div>\n<div>\n<p id=\"speakable-summary\" class=\"wp-block-paragraph\">OpenAI released solutions to three blockbuster math problems that have long vexed researchers yesterday. One was a surprise rejection of the Exponential Time Hypothesis (ETH), a durable assumption in computer <a href=\"https:\/\/buradabiliyorum.com\/en\/category\/sciencee\/\" data-internallinksmanager029f6b8e52c=\"5\" title=\"Science\" target=\"_blank\" rel=\"noopener\">science<\/a> that plays a large role in how we understand what is difficult to compute.<\/p>\n<p class=\"wp-block-paragraph\">As with previous proof-drops from the frontier lab, scientific communities responded with a mixture of thrill and dismay. Anthropic mathematician Levent Alp\u00f6ge <a rel=\"nofollow\" target=\"_blank\" rel=\"nofollow\" href=\"https:\/\/x.com\/__alpoge__\/status\/2114838067953770981\">suggested<\/a> that OpenAI was basing its solutions from pre-existing work, and hours later, Anthropic subsequently <a rel=\"nofollow\" target=\"_blank\" rel=\"nofollow\" href=\"https:\/\/github.com\/anthropics\/formal-math\/tree\/main\/eth\">released<\/a> its own refutation of ETH.<\/p>\n<p class=\"wp-block-paragraph\">However, OpenAI\u2019s process is evolving. This time, the lab <a rel=\"nofollow\" target=\"_blank\" rel=\"nofollow\" href=\"https:\/\/openai.com\/index\/building-scientific-understanding-with-academic-communities\/\">structured its releases<\/a> differently for each of the three disciplines involved: Mathematicians got the work dropped on GitHub; the computer scientists formed a working group, asked for the proofs to be shared publicly and OpenAI to fund a conference to discuss them; the physicists formed a working group that will determine how their result will be released.<\/p>\n<p class=\"wp-block-paragraph\">MIT Professor Ryan Williams is the computer scientist who is organizing his field\u2019s response to the new finding. Williams, whose work focuses on these questions of computational complexity, has criticized OpenAI\u2019s <a href=\"https:\/\/buradabiliyorum.com\/en\/category\/download-scripts-themes-apps\/\" data-internallinksmanager029f6b8e52c=\"9\" title=\"Download Scripts &amp; Themes &amp; Apps\" target=\"_blank\" rel=\"noopener\">app<\/a>roach in the past, <a rel=\"nofollow\" target=\"_blank\" rel=\"nofollow\" href=\"https:\/\/x.com\/rrwilliams\/status\/2108224296015528135\">calling<\/a> its proof dump earlier this October a \u201cDDOS attack on mathematicians.\u201d<\/p>\n<p class=\"wp-block-paragraph\">However, he agreed to collaborate with the frontier labs in order to help shepherd ideas that are vital to the field, he told TechCrunch. The lab asked him to help interpret the solution, along with UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published the ETH in 1999.<\/p>\n<p class=\"wp-block-paragraph\">Their first step was to release <a rel=\"nofollow\" target=\"_blank\" rel=\"nofollow\" href=\"https:\/\/docs.google.com\/document\/d\/1adB0IhJgLzsmbfCgoLrtoJTjnlPf74UnyjMo35P5JHo\/edit?tab=t.0\">an open letter<\/a> calling for feedback from scientists interested in these problems and a discussion of the norms around AI contributions to their work. <\/p>\n<p class=\"wp-block-paragraph\">\u201cSome parts [of OpenAI\u2019s proof] are, maybe you could say routine, but then yes, there are two or three alien-looking parts, and it\u2019s exactly these parts that that I saw that made me think, wow, this is something that the whole community needs to work on together,\u201d Williams told TechCrunch.<\/p>\n<h2 class=\"wp-block-heading\" id=\"h-are-you-down-with-p-vs-np\"><span class=\"ez-toc-section\" id=\"Are_you_down_with_P_vs_NP\"><\/span>Are you down with P vs NP?<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p class=\"wp-block-paragraph\">The ETH is part of a broader class of problems known as P vs NP, which has animated computer science and many other fields for decades. Reductively, researchers are trying to understand if any problem whose solution can be easily verified (NP) can also be easily solved (P). <\/p>\n<p class=\"wp-block-paragraph\">A simple example is the <a href=\"https:\/\/buradabiliyorum.com\/en\/category\/game\/\" data-internallinksmanager029f6b8e52c=\"7\" title=\"Game\" target=\"_blank\" rel=\"noopener\">game<\/a> Sodoku: Once a solution to a puzzle is in place, it can be quickly verified, but finding the solution is time-consuming. That dynamic is true across a range of important problems, and the insight underpins cryptographic systems: When you have the key to an encoded message, you can reveal it, but actually cracking an effective code takes too long to be useful.<\/p>\n<p class=\"wp-block-paragraph\">However, scientists have yet to prove whether that is always true. \u201cP = NP is saying that, not only can you verify Sudoku solutions when they exist, you can just generate them,\u201d Williams said. \u201cP = NP is asserting that this is true for every single problem you can verify quickly \u2014 if you can verify it quickly, you can solve it quickly. So this just seems that just seems too good to be true.\u201d<\/p>\n<p class=\"wp-block-paragraph\">That\u2019s why most scientists assume that P \u2260 NP. ETH provided evidence for that. It basically says that even the fastest computer algorithm needs exponentially more time to find a solution as the number of variables grow in a specific class of tricky logic puzzle.<\/p>\n<p class=\"wp-block-paragraph\">The claims from OpenAI and Anthropic is that their models have come up with algorithms that solve those puzzles in \u201csub-exponential\u201d time, meaning faster than the speeds previously thought possible. If true, they may have proven the EFT to be false \u2014 refuted it, in scientific terms \u2014 and maybe opened up a path for algorithms that <a href=\"https:\/\/buradabiliyorum.com\/en\/category\/general\/\" data-internallinksmanager029f6b8e52c=\"3\" title=\"General\" target=\"_blank\" rel=\"noopener\">general<\/a>ly perform P = NP.<\/p>\n<p class=\"wp-block-paragraph\">\u201cEvery computer scientist should probably put a a little more weight on the plausibility of P = NP, but one\u2019s weight may vary,\u201d Williams said. \u201cI do think that it kind of calls into question a lot of the intuitions that we thought we had about \u2026 how tractable [hard NP problems] are. I also think that this is probably not the final answer either. I don\u2019t think that OpenAI\u2019s algorithm could possibly be the best algorithm you can get.\u201d<\/p>\n<h2 class=\"wp-block-heading\" id=\"h-the-work-ahead-for-computer-scientists\"><span class=\"ez-toc-section\" id=\"The_work_ahead_for_computer_scientists\"><\/span>The work ahead for computer scientists<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p class=\"wp-block-paragraph\">The durability of ETH has lead to it being included in many scientific papers over the past decade that will need to be revisited if the AI labs claims that they\u2019ve proven it wrong holds up, Williams said.<\/p>\n<p class=\"wp-block-paragraph\">\u201cThis is partly why I was asking or pushing OpenAI to support a conference on this \u2014 it\u2019s going to affect many researchers\u2019 works, and we need to figure out, okay, what happens next besides understanding the algorithms, we need to understand, what should the foundations be that we had before?\u201d he said.<\/p>\n<p>Before scientific concerns, there are cybersecurity questions. Williams said that an improved algorithm could imply that cryptographic systems relying on certain key sizes could be considered broken. So one of the first questions he asked OpenAI science lead Dan Roberts \u201cwas if they had checked that that this affects any crypto systems \u2026 is anything insecure now? And apparently, they checked, and they were reasonably confident that this didn\u2019t \u2026 imply any breaks.\u201d<\/p>\n<p class=\"wp-block-paragraph\">This new AI paradigm of scientific discovery is still a work in progress, but Williams says he is optimistic despite real concerns, particularly about training the next generation of scientists. Being a computer scientist who does high level math has perhaps made the adjustment easier for him than for pure mathematicians.  <\/p>\n<p class=\"wp-block-paragraph\">Still, he says AI is \u201cforcing people to be a little more ambitious about the kind of work that they do, and to think more deeply about okay, if all the things I used to work on are now low hanging fruit for AI, how can I raise the bar for the the kind of scientific questions I want to ask?\u201d<\/p>\n<\/div>\n<p><em>When you purchase through links in our articles, we may earn a small commission. This doesn\u2019t affect our editorial independence.<\/em><\/p>\n<blockquote><p><strong><span style=\"color: #ff6600;\">If you liked the article, do not forget to share it with your friends. Follow us on\u00a0<span style=\"color: #ff0000;\"><a style=\"color: #ff0000;\" href=\"https:\/\/news.google.com\/publications\/CAAqBwgKMN63nwsw68G3Aw\" target=\"_blank\" rel=\"nofollow noopener noreferrer\">Google News<\/a><\/span>\u00a0too, click on the star and choose us from your favorites.<\/span><\/strong><\/p><\/blockquote>\n<blockquote>\n<p style=\"text-align: center;\"><strong>If you want to read more like this article, you can visit our <span style=\"color: #ff9900;\"><a style=\"color: #ff9900;\" href=\"https:\/\/buradabiliyorum.com\/en\/category\/technology\/\" target=\"_blank\" >Technology<\/a><\/span> category.<\/strong><\/p>\n<\/blockquote>\n<p><span style=\"color: black;\"><a style=\"color: #ff9900;\" href=\"https:\/\/techcrunch.com\/2026\/10\/27\/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean\/\" target=\"_blank\" >Source<\/a><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>OpenAI released solutions to three blockbuster math problems that have long vexed researchers yesterday. One was a surprise rejection of the Exponential Time Hypothesis (ETH), a durable assumption in computer science that plays a large role in how we understand what is difficult to compute. As with previous proof-drops from the frontier lab, scientific communities&#8230;<\/p>\n","protected":false},"author":1,"featured_media":749961,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"https:\/\/techcrunch.com\/wp-content\/uploads\/2026\/04\/Screenshot-2026-04-14-at-7.00.44-PM.png?resize=1200,783","fifu_image_alt":"","footnotes":""},"categories":[18],"tags":[77337,61594],"class_list":["post-749960","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-technology","tag-ai","tag-exclusive"],"_links":{"self":[{"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/posts\/749960","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/comments?post=749960"}],"version-history":[{"count":0,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/posts\/749960\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/media\/749961"}],"wp:attachment":[{"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/media?parent=749960"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/categories?post=749960"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/tags?post=749960"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}