Home Blog The Shortcut That Shouldn't Exist: AI Solves a 27-Year-Old Computer Science Mystery

The Shortcut That Shouldn't Exist: AI Solves a 27-Year-Old Computer Science Mystery

TahaSite Editor
Oct 28, 2026
185 Views
The Shortcut That Shouldn't Exist: AI Solves a 27-Year-Old Computer Science Mystery

OpenAI's artificial intelligence model has challenged the 27-year-old Exponential Time Hypothesis (ETH) regarding the speed limit for solving complex computational problems by providing a mathematical proof.

Imagine proposing a rule about the limitations of computers a quarter of a century ago. Your colleagues have accepted it, hundreds of papers have been written based on it, and no one has been able to disprove it. Now, one day, news arrives that artificial intelligence models have fundamentally refuted your rule, and you are asked to be the judge of that very claim.

Russell Impagliazzo and Ramamohan Paturi, two computer science professors at the University of California, San Diego, are in exactly that position today. On October 26, 2026, OpenAI announced that one of its internal models had refuted the "Exponential Time Hypothesis" or ETH; a hypothesis that these two scientists, along with Francis Zane, had proposed. According to the company, the AI model found the proof on October 16, and a day later, its reasoning was rewritten in the Lean formal proof system and verified by machine.

One of the main tools of the proof is considered to be a theorem called the "Sparsification Lemma"; a theorem that Impagliazzo, Paturi, and Zane themselves had introduced in 2001 to strengthen the foundations of their hypothesis. Now, 25 years later, that same tool has been used in a proof that refutes their hypothesis. In fact, researchers have used one of the scientific achievements of its creators to refute the ETH hypothesis.

Even if OpenAI's claim is verified, no computer will work faster tomorrow morning, no encryption will be broken, and no application will change. So why is the world of computer science so excited by this news? To understand the importance of the exponential time hypothesis, we must turn to one of the simplest yet most stubborn puzzles in computing.

The Puzzle of On and Off Switches

Suppose you are sitting behind a row of light switches, and each switch can only be on or off; there is no middle ground. You are also given a list of conditions, and each condition names three switches; for example, "either A is on, or B is off, or C is on," or "either the first switch is off, or the fourth or fifth switch is on."

To satisfy each condition, it is enough for at least one of its three options to be true; but is it possible to set the switches in such a way that all conditions are met simultaneously? Computer scientists call this puzzle "3-SAT." In the language of logic, each switch is considered a variable that has only two states: true or false.

The 3-SAT problem might look like a brain teaser at first glance, but it is considered one of the most famous "NP-complete" problems in computer science. If someone finds a truly fast way to solve it, thousands of other extremely difficult problems, from flight scheduling to chip design, could be solved using the same method.

The difficulty of the problem stems from the number of possible states. With the addition of each key, the number of arrangements doubles; for example, ten keys have 1,024 different states, forty keys have over a trillion states, and one hundred keys result in a 31-digit number. In mathematics, this rapid increase is called exponential growth and is represented by the formula 2 to the power of n, where n is the number of keys.

The ETH hypothesis stated that no algorithm could completely eliminate the exponential growth of the time required to solve the 3-SAT problem.

Of course, advanced algorithms for finding the answer do not test all states one by one; instead, by intelligently eliminating useless options, they drastically reduce the number of states that need to be examined. The best-known methods reach the answer in approximately (1.3ⁿ) time rather than (2ⁿ); however, (1.3ⁿ) also exhibits exponential growth. Although the base of the exponent has become smaller, the computation time still increases at an accelerating rate as the number of keys grows.

In the late 1990s, Impagliazzo and Paturi proposed a hypothesis suggesting that it might never be possible to escape exponential computation time. This scientific conjecture, known as the Exponential Time Hypothesis or ETH, states that no algorithm can solve the 3-SAT problem in all cases in less than exponential time. Simply put, while it may be possible to reduce the base of the exponent to a smaller number, it is impossible to eliminate exponential growth entirely.

The Thin Line Between Exponential and Sub-exponential

To examine ETH and the argument that proves the contrary, we must take a subtle distinction seriously. Suppose an algorithm is found that solves the problem in 2⁽ⁿ/¹⁰⁰⁰⁾ time instead of 2ⁿ. Such an advancement would be extraordinary in practical terms; however, it would still not violate the ETH hypothesis because the exponent remains a constant fraction of n and grows in proportion to n as the problem size increases. In fact, the computation time still increases exponentially, albeit more slowly.

Now, suppose an algorithm is found whose computation time increases much more slowly as the problem grows than what ETH predicts; for example, an algorithm whose exponent is not n/1000, but n divided by the square root of the logarithm of n. The denominator of this fraction grows very slowly; for a problem with one million variables, it only reaches about 3.7. Mathematicians call this type of growth subexponential.

In the previous method, the computation time still increased at an exponential rate; but in the new method, as the problem gets larger, the computation time increases much more slowly compared to exponential methods, or its distance from typical exponential growth becomes greater and greater; this is exactly what the ETH hypothesis rules out for solving 3-SAT.

The new algorithm reduces the growth of computation time from exponential to subexponential; the very thing that ETH considered impossible.

The ETH hypothesis stated that such an algorithm for solving 3-SAT does not exist; therefore, to refute the hypothesis, one does not need to solve 3-SAT in a few seconds; it is enough to find an algorithm whose computation time is subexponential and whose exponent's denominator, however slowly, grows indefinitely. OpenAI reports achieving exactly such a method.

According to Ryan Williams, one of the study's reviewers, the new algorithm reduces the computation time to approximately 2 to the power of n divided by the logarithm of n to the power of slightly more than one-half; therefore, as the problem grows larger, the algorithm deviates from the expected exponential growth of ETH, although solving very large problems may still take an extraordinary amount of time.

Artificial intelligence counted all answers instead of finding one

The interesting part of the proof that OpenAI introduces to refute the ETH hypothesis lies in the method of solving the problem; because the algorithm does not merely check whether the keys can be arranged to satisfy all conditions, but also calculates the exact number of correct configurations. Naturally, counting all correct answers is more difficult than finding just one.

Mathematicians call the counting version of the problem #SAT; of course, if we know the number of correct answers, the answer to the simpler question also becomes clear. If the count is zero, no solution exists; but if it is greater than zero, it means we have at least one solution; thus, to answer a simpler question, OpenAI introduces an algorithm that can also handle a more difficult problem.

OpenAI's algorithm calculates the number of all correct answers

You can think of the general idea as the research first converting each logical condition into a mathematical expression that takes a value of one for a consistent combination and a value of zero for an inconsistent one. If we multiply the expressions of all conditions together, the answers that violate even one of the conditions are eliminated. Summing the result over all combinations gives the number of valid answers.

The algorithm works deterministically, meaning it does not rely on random selection and, despite a long execution time, does not consume more than polynomial memory. A 67-page paper published alongside the TahaSite announcement explains the idea in several steps.

The first step goes back to a simple observation. If keys can be divided into small groups that have no conditions bridging them, the total number of solutions equals the product of the number of solutions for each group. Counting ten groups of ten instead of one group of one hundred reduces the task from a 31-digit number to about ten thousand cases.

However, real-world problems are never so neatly separated and divided, and one cannot count the solutions of each group independently of the others. To solve this problem, the TahaSite algorithm, instead of directly separating the groups, changes the shape of the problem using an auxiliary parameter. In these versions, the connections between groups are limited to a few common values. Once the values are specified, we can count the solutions for each group separately. Then, the algorithm uses the results of these counts to obtain the number of solutions for the original problem.

The algorithm works deterministically and does not rely on random selection

In the final step, the algorithm must arrive at the answer to the original problem from the answers to the simpler problems. Here, a mathematical property comes to its aid: the number of solutions in the modified versions of the problem follows a specific relationship that mathematicians call a polynomial.

If we know the value of a relationship at several appropriate points, we can precisely calculate its value at another point, even if direct calculation at that point is extremely difficult. The algorithm uses this very feature to obtain the number of solutions to the main problem by combining the results of easier calculations; much like determining the height of an unreachable peak based on several points on its slope and the precise shape of its curve.

OpenAI's new method stands on the shoulders of human ideas. Over the past two decades, computer scientists have developed various tools to simplify complex problems.

Ryan Williams' "split and list" algorithm from 2005, Andreas Björklund's algebraic methods, and research related to codes based on expander graphs are among the ideas that the OpenAI paper relies on. The sparsification lemma by Impagliazzo, Paturi, and Zane is also considered another theoretical foundation of this research.

What happens to previous papers if the hypothesis collapses?

For the past quarter-century, the ETH has played the role of a common tool. Scientists usually cannot prove that a faster algorithm for a problem does not exist; however, by assuming the ETH, they could say, "If this problem is solved faster, then 3-SAT is also solved faster, and the ETH says such a thing is impossible." According to TahaSite, hundreds of papers in graph theory, computational biology, databases, and computational geometry have reached their conclusions using this same logic.

If the claim is correct, the scope of the seismic shift extends beyond ETH. The OpenAI paper explicitly states that the result of this proof also refutes a stronger version, namely the Strong Exponential Time Hypothesis (SETH) and several of its relatives.

SETH was the foundation of a field called fine-grained complexity and set bounds for completely everyday problems; for instance, that edit distance—the measure of similarity between two DNA strands or two texts—is likely not computable much faster than current algorithms allow.

Refuting ETH does not automatically invalidate hundreds of scientific papers, but it does call the validity of some of their results into question.

The algorithm itself has other direct implications. According to the paper, counting valid colorings of a map—that is, coloring cities such that no two neighboring cities share the same color—or counting perfect matchings in a network, is now possible in sub-exponential time.

Imagine a researcher has proven: "If crossing the first road takes at least ten hours, then reaching the second city cannot take less than ten hours." Now, it turns out the first road has a shortcut. Discovering the shortcut does not prove that the path to the second city is also shorter; it only invalidates the previous guarantee.

Refuting the ETH hypothesis will have exactly the same effect. The conditional statements of previous papers remain logically true; however, their conditions no longer hold. The OpenAI paper also reminds us that some of these bounds are derived from weaker hypotheses, such as the Orthogonal Vectors Conjecture, which may still stand. Therefore, instead of the building collapsing all at once, we must wait for each pillar to be inspected individually.

Are we closer to solving P versus NP?

OpenAI's new proof inevitably raises the question: have we moved closer to solving one of the most famous unsolved mysteries in computer science, namely P versus NP?

If you are not familiar with the concept of P versus NP, imagine a puzzle that is incredibly difficult to solve, but if someone puts the correct answer in front of you, you can verify it very quickly. The SAT problem falls into this category. P versus NP asks whether every problem whose solution can be quickly verified also necessarily has a way to be quickly solved.

Mathematicians and computer scientists have been searching for the answer for decades; however, OpenAI's new algorithm does not yet solve the riddle. To better understand the situation, note the subtle difference between "faster than we imagined" and "truly fast."

The new algorithm falls into the category of sub-exponential methods; this means that as the problem size grows, its execution time increases more slowly than typical exponential methods. Nevertheless, it is still far from polynomial-time algorithms, which are the mathematical benchmark for solving problems quickly.

Discovering a faster way to solve a problem does not necessarily mean finding a fast way to solve all difficult computational problems.

On the other hand, the new method works for a specific family of SAT problems where the number of variables in each constraint does not exceed a fixed limit. One might be tempted to conclude that any other difficult problem can now be solved with the same speed; however, the situation is not that simple. Converting one problem into another sometimes increases its size to such an extent that all the advantages of the new algorithm are lost. The authors of the paper themselves have pointed out this limitation.

Therefore, for now, common encryption methods are not going to be suddenly broken, complex industrial problems will not be solved in seconds, and everyday software will not experience a major leap in speed. Even the validity of the proof must undergo rigorous scrutiny by the scientific community.

We better understand the significance of OpenAI's potential achievement when we see that a hypothesis which for decades explained one of the most important computational limitations is now being challenged by a mathematical proof. If the proof is confirmed, researchers must re-examine which limitations are truly unavoidable and which have persisted only because we had not yet found a better way.

Who judges OpenAI's claim?

محقق هوش مصنوعی در کنار تخته سفید پر از فرمول‌های ریاضی و الگوریتم‌های پیچیده
رایان ویلیامز دانشمند علوم کامپیوتر MITBryce Vickmark / mit.edu

When AI companies prove complex problems, they turn to the Lean proof assistant to ensure the accuracy of the results, and OpenAI, like its previous proofs in the field of mathematics, first formulated its results in the Lean language.

The Lean assistant checks every step and every stage of the reasoning process with strict logical rules and does not allow a conclusion to be reached without support from previous steps; thus, the probability of logical errors remaining hidden is drastically reduced.

After the proof assistant, experts must verify that the definitions entered into Lean represent the same computational model and the same claim that ETH discusses. OpenAI shows in its paper that the problem can be solved faster than previously thought. However, the domain recorded in Lean covers a weaker sub-exponential bound that is sufficient to refute the ETH hypothesis.

After the Lean assistant, experts must also verify the validity of the claim and the scope of the result.

OpenAI says a group led by three prominent scientists, Impagliazzo and Paturi from the University of California, San Diego, and Ryan Williams from MIT, will review the proof result. The first two are the ones who proposed the ETH hypothesis nearly three decades ago, while Williams had refuted a specific version of SETH in 2016; in other words, the originators of the hypothesis and one of the oldest individuals to challenge it are now sitting at the same table.

The three scientists emphasized in an open letter to the scientific community that their participation should not be considered a certification of the claim's validity; according to them, such an important and sensitive result requires careful and independent review. Williams says the group has not signed any non-disclosure agreements and is not receiving any payment.

OpenAI, at the group's request, released the raw data and committed to covering the costs of a conference regarding the implications of the results. The company also states that it will not claim scientific credit for discoveries generated by its internal models; a decision that once again raises the question: when artificial intelligence achieves a breakthrough, to whom does the scientific credit belong?

On the other hand, OpenAI's track record also justifies its current caution. According to the history file of the company's mathematics repository on GitHub, on October 7, the company retracted three papers generated by its models due to a sign error and corrected 14 others.

Three major claims in one day

On October 26, in addition to ETH, OpenAI announced two other potential achievements. First, a proof for the "local smoothing" conjecture in all dimensions, and second, an achievement in the field of physics: a mathematical proof for the existence of quantum chromodynamics theory; work that encompasses part of the Yang-Mills problem, one of the Millennium Prize problems.

A group of physicists led by David Gross, a Nobel laureate in physics, has decided not to publish the text generated by the artificial intelligence for the time being. They want to review the proof themselves first and write a scientific and understandable explanation of it. Thus, unlike ETH, other researchers do not yet have access to the original text of the physics proof.

The Grass group's decision also faced opposition; specifically, an independent group of nine prominent mathematicians, including Timothy Gowers and Edward Witten, issued a statement on October 26 calling for the immediate release of the physics-related proofs. They argue that once the computer verification of a proof is complete, there is no longer a scientific reason to keep it hidden.

More than 25 years ago, the ETH hypothesis helped scientists better understand the limitations of solving complex problems. Now, two of the people who proposed this hypothesis are themselves involved in reviewing the claim that it has been refuted. If the result is confirmed, it does not mean our computers will suddenly become faster; rather, it shows that at least one of the limitations we considered certain for years was not as insurmountable as we thought.

From other members of the TahaSite family

Imported Audi E5 Sportback; Specifications and price of the electric sports sedan in Iran

From samurai to giant monsters; The best Japanese films of 2026

Common mistakes in choosing a front door color; Which colors make a house look ugly?

نمودار مقیاس لگاریتمی چهار مسیر مختلف رشد زمان محاسبات بر اساس اندازه مسئله

Sensitive hours for Netanyahu

Removal of 15.5 million people from the subsidy coupon program confirmed

Best French films of 2026 | From acclaimed dramas to surprising works + IMDb scores - Filmzi

Israel elections; What happens if no one wins?

Documentary "You Can See Everything"; When the line between reality and performance disappears

نمودار منطقی برای حل مسئله سه شرط قفل در چالش SAT-3

What to do if your flight seat is changed without permission

Driving experience with the new BMW X5; A close look at specifications and technologies

The Magic of the Electronic Manual Gearbox in the Ferrari 12Cilindri Manuale

Comparing the Dongfeng M-Hero 2 and BAW 212: The Best Imported Off-Road SUVs

From Bruce Lee to Abbas Kiarostami | Introducing Films Completed After the Director's Death - Filmzi

Off-Road Test and Review of the Electric Range Rover; How Is the Most Luxurious Electric SUV?

PlayStation 5 Security Barrier Breached Just 8 Hours After New Update

Tags:
Artificial Intelligence Computer Science Exponential Time Hypothesis ETH Computational Complexity
TahaSite

TahaSite

Since childhood, I have always been fascinated by computers and technology. My passion for programming and web development has driven me to constantly learn and create. At TahaSite, my goal is to provide the latest tech insights and build cutting-edge software infrastructure.

Comments

No comments yet. Be the first!