# AI Says It Cracked a 27-Year-Old Computer Science Puzzle Author: Sachin Bhatnagar | Published: 2026-11-06 | Canonical: https://stacksauce.dev/blog/ai-says-it-cracked-a-27-year-old-computer-science-puzzle ## **AI Says It Cracked a 27-Year-Old Computer Science Puzzle. How Should You Read News Like This?** A few weeks ago, two AI companies got into a race to disprove the same idea in computer science. If you had told a computer science professor in 2016 that this would be the hot gossip of 2026, they would have asked you to sit down and drink some water. On 26 October 2026, OpenAI announced that its AI models had produced proofs for three very hard problems in mathematics, computer science and physics. The one that got the most attention was a claim that something called the Exponential Time Hypothesis is false. Within hours, Levent Alpöge, a mathematician at Anthropic, suggested that OpenAI's work was built on existing research. Then Anthropic released its own proof against the same hypothesis. If you are a beginner, your head might be spinning. What is this hypothesis? Is it true that AI is now doing original research? And should this change anything about how you learn? Let me break it down slowly. I also want to use this story to teach you something more useful than the news itself, which is how to read big AI claims without getting fooled. ### **First, what is the Exponential Time Hypothesis?** Let us start with a simple idea. Some problems are easy to check but hard to solve. Think of a Sudoku puzzle. If I give you a finished Sudoku, you can check it in a minute. Just look at each row, column and box. But solving a fresh, difficult Sudoku from scratch can take a long time. Computer scientists have been studying this gap for decades. In 1999, two researchers, Russell Impagliazzo and Ramamohan Paturi, made a careful bet about it. Their bet is called the Exponential Time Hypothesis, or ETH. A hypothesis is an idea that experts believe is true but have not proved. ETH says that for a certain family of logic puzzles, no computer program can ever be dramatically faster than trying a huge number of possibilities. The key word is "exponential". It means the work multiplies every time the puzzle grows a little. Think of a number lock on a suitcase. A lock with 3 dials has 1,000 possible codes. Add one more dial and you have 10,000 codes. Add another and you have 100,000. Each small step makes the work ten times bigger. That kind of growth gets out of hand very quickly. So ETH basically says, "For these puzzles, there is no clever shortcut. The work will always explode as the puzzle grows." ### **Why do people care so much?** ETH is like a foundation stone. Many research papers assume it is true and build their results on top of it. Ryan Williams, a professor at MIT who is helping to check the claims, told TechCrunch that many of these papers "will need to be revisited" if the claims hold up. In simple words, if the foundation stone moves, a lot of the building has to be inspected again. There is also a practical worry. Some kinds of encryption depend on certain problems staying hard. Encryption is the method that scrambles your data so that only the right person can read it. It protects your passwords, your payments and your messages. Williams said he asked OpenAI about this. According to him, OpenAI's team checked and "were reasonably confident" that the result did not break any encryption systems. That check has not been independently confirmed yet. Still, nobody credible is saying that your bank account is in danger this week. So please do not change your UPI PIN in panic. ### **So is it true? Has AI really done this?** Here is the honest answer. We do not know yet. At the time I am writing this, the claims have not gone through peer review. Peer review is the normal process in science where other experts carefully check a piece of work before it is accepted. A group led by Williams, Impagliazzo and Paturi, the two researchers who first proposed ETH, is now examining OpenAI's proof. OpenAI says its result was checked using a tool called Lean. Lean is a computer program that checks maths proofs line by line. It works like a very strict teacher who will not let you skip a single step. That is a good sign. But one news site, Tech Insider, made an important point. Lean can confirm that a proof is correct for the exact statement written into it. People still need to check that this exact statement matches the big claim in the headline. Williams himself was interesting to listen to. He said some parts of the proof look "routine", but there are "two or three alien-looking parts." He also said, "I don't think that OpenAI's algorithm could possibly be the best algorithm you can get." In other words, even if the result holds, this is probably the beginning of the story. The other claims also deserve a careful look. OpenAI said its models proved a famous problem in mathematics called the local smoothing conjecture. Alex Iosevich, a maths professor at the University of Rochester, called it a "historic development", according to Al Jazeera. But Tech Insider pointed out that OpenAI's headline wording was broader than its own fine print. For the physics claim, the full materials have not been released yet. So the fair summary is this. Something big may have happened. Respected experts are treating it with care. And nobody outside these companies has confirmed it yet. ### **How to read big AI claims: my five-question test** You will see headlines like this every week now. "AI solves X." "AI replaces Y." "AI discovers Z." Some of them will be true. Many will be half true. A few will be pure marketing. Here are five questions I ask myself before I believe any big AI claim. You can use them too. 1. **Who is making the claim?** If the company that built the AI is also announcing the result, be a little careful. They have a reason to make it sound as big as possible. 2. **Who has checked it?** Look for names of independent experts who are not paid by that company. Look for what they actually said, in their own words. 3. **What exactly is being claimed?** Headlines are short. The real claim is often narrower. Read the details, or at least read someone who has read them. 4. **What do the critics say?** Every big claim has sceptics. In this story, Anthropic's mathematician questioned OpenAI's work within hours. That kind of argument is healthy, and it helps you see the full picture. 5. **What changes for me today?** Often the honest answer is "nothing yet". That is fine. Waiting two or three weeks for experts to react is a perfectly smart move. This is what we call critical thinking. In my opinion, it is going to be one of the most valuable skills of this decade. AI tools will produce more and more content. People who can judge that content will be worth a lot. ### **"If AI can do this, why should I learn anything?"** I can already hear this question from some of my students. Now most will say, "If AI can disprove theorems that experts could not, then learning is pointless. The machines will do everything." Partly agreed. AI is clearly getting better at difficult reasoning tasks, and that will change many jobs. But look at who is being called to check these proofs. It is people like Ryan Williams, Russell Impagliazzo and Ramamohan Paturi. These are people who spent decades learning the basics deeply. When the AI produced something strange, they were the only ones who could say, "This part looks routine, and this part looks alien." As AI does more of the work, the people who understand the fundamentals become the people who judge it. Someone has to know whether the answer is right. ### **What this means for you** If you are a beginner in tech, here is what I would take away from this story. - **Learn how algorithms grow.** An algorithm is simply a set of steps to solve a problem. In computer science, we study how the work grows as the input grows. This is called Big O notation. The name sounds scary, but the idea is the same suitcase lock from earlier. - **Build a habit of checking.** When ChatGPT or Claude gives you code or an answer, test it. Run it. Question it. Treat AI like a very fast junior colleague who is sometimes confidently wrong. - **Follow real experts.** Look for researchers and engineers who explain their reasoning. Choose them over accounts that only post exciting headlines. - **Stay curious.** Stories like this are a wonderful excuse to learn something new. Search for "P versus NP explained simply" this weekend. It is one of the most famous unsolved questions in computer science, and ETH is closely connected to it.