Free Intensive Nov 21–22Free 2-day hands-on Vibecoding Intensive on Nov 21–22 at 16:00 MSK (Sat–Sun) · Live Cohort 3 starts Nov 23Join Free →Cohort 3 (Nov 23)

OpenAI says its AI disproved the ETH hypothesis that hundreds of research papers rely on

OpenAI says its AI has disproved the exponential time hypothesis (ETH), which holds that the runtime for a class of logic problems inevitably grows exponentially. Think of building a shift schedule for a hundred staff with a hundred constraints: ETH claims there is no way to beat full brute-force enumeration, and hundreds of research papers are built on that claim. The result was obtained on October 16, formalized in Lean on October 17, and is now being examined by experts, including two authors of the hypothesis. For now, this is a claim, not a ready-made speedup for your solvers.

AI-processed from TG: @ai_machinelearning_big_data (Machinelearning); edited by Hamidun News
OpenAI says its AI disproved the ETH hypothesis that hundreds of research papers rely on
Source: TG: @ai_machinelearning_big_data (Machinelearning). Collage: Hamidun News.
Listen to article
Article Fact Sheet & Key Figures
ParameterDetails
Primary sourceTG: @ai_machinelearning_big_data (Machinelearning) ↗
Editor-in-Chief
Key metric #1Lean is a program that checks a proof step by step, so no one has to take the author's word for it
Key metric #2The review group includes two of the original ETH authors
Key metric #3Practical algorithms based on the result will require separate research

Imagine building a shift schedule for a hundred employees: each has their own preferences, vacations, and workload limits. The more people and conditions there are, the more variants you have to check. Theorists have been asking for decades whether this explosion of options can be avoided or whether it is inevitable. The exponential time hypothesis, or ETH, answered that it is inevitable. OpenAI now claims its AI has found a refutation of that hypothesis.

What ETH is and why it matters

ETH concerns a class of logic problems where you must assign values to variables so that all conditions hold at once. The hypothesis assumes that for such problems the growth of computation time cannot be avoided. Roughly speaking, each new variable noticeably increases the work, and no trick cancels that growth.

This is not just an elegant guess. According to OpenAI, hundreds of research papers rest on it. The logic runs like this: "if ETH is true, then no fast algorithm for this problem exists either." That is how lower bounds on complexity are built for many other problems. If the foundation cracks, a whole layer of conclusions that leaned on it comes into question.

What OpenAI actually claimed

The company reports that its AI found a refutation of ETH. The result was obtained on October 16, and on October 17 it was formalized in Lean. Lean is a proof-verification system: each step is written in a strict language, and the program itself confirms that the conclusion follows from the previous steps. It does not require trusting the author on their word, whether that author is a human or a model.

The result is being checked by more than a machine. A group of experts is studying it, and that group includes two authors of the original hypothesis. This is a serious test: the people who formulated ETH are looking for weak points in a proof that breaks it.

Still, OpenAI is cautious. The company asks that its AI's manuscripts be treated as source research material, not a final verdict. Independent review is ongoing. The announcement was part of a broader message about AI-driven scientific results, but the ETH story is the closest to developers' everyday work, because it concerns how fast entire classes of problems can in principle be solved.

What this means for practitioners

First, expectations. OpenAI itself writes that finding practically useful algorithms based on the result will require further research. This does not mean your logic solvers or planners will run faster tomorrow. The theoretical fact that exponential growth is not mandatory does not yet give you concrete fast code you can ship to production. The announcement contains no details on how the refutation works or where it applies, and until those are published, drawing conclusions about practical impact is premature.

But a few lessons are already visible:

  • Formal verification helps you trust AI. When a model produces a complex result, manual review does not scale. Lean gives a mechanical criterion: a proof either goes through or it doesn't. A similar approach can apply to critical code and protocols.
  • Don't rely blindly on "known to be infeasible." If your product or architectural decision rests on the claim that a problem cannot be solved quickly, it is worth knowing which hypothesis that claim depends on. Some such claims are tied precisely to ETH.
  • Separate claims from facts. While expert review is underway, this is the company's claim, not a closed question. The history of science contains plenty of loud proofs that did not survive careful scrutiny.

For the AI industry, the signal is different. Models are starting to propose results that experts take seriously and check with the help of the original researchers. If the review confirms the refutation, it will be a strong argument that AI can find something new, not just reproduce what humans have found. If it does not, we will have a clear example of how such claims should pass through a filter.

Either way, it is worth waiting for the expert group's published analysis. That is what will show what the refutation rests on and what it changes for practice.

Story

Key Questions Answered

What ETH is and why it matters?

ETH concerns a class of logic problems where you must assign values to variables so that all conditions hold at once. The hypothesis assumes that for such problems the growth of computation time cannot be avoided. Roughly speaking, each new variable noticeably increases the work, and no trick cancels that growth. This is not just an elegant guess. According to OpenAI, hundreds of research papers rest on it.

What OpenAI actually claimed?

The company reports that its AI found a refutation of ETH. The result was obtained on October 16, and on October 17 it was formalized in Lean. Lean is a proof-verification system: each step is written in a strict language, and the program itself confirms that the conclusion follows from the previous steps. It does not require trusting the author on their word, whether that author is a human or a model. The result is being checked by more than a machine.

What this means for practitioners?

First, expectations. OpenAI itself writes that finding practically useful algorithms based on the result will require further research. This does not mean your logic solvers or planners will run faster tomorrow. The theoretical fact that exponential growth is not mandatory does not yet give you concrete fast code you can ship to production. The announcement contains no details on how the refutation works or where it applies, and until those are published, drawing conclusions about practical impact is premature.

ZK
Zhemal Khamidun — CPO at Alpina Digital, product manager of AlpinaGPT. Building AI products since 2019. Hamidun News is a pet project that grew into a production aggregator with 6,000+ readers.
✦ Unified AI Workspace · Nomad

Test Frontier LLMs & Autonomous Agents in One Workspace

Run Claude Opus 5.5, GPT-6, Gemini 3.1, and DeepSeek side-by-side in Nomad AI (nomadnet.ai) — unified model routing, deep research, and multimodal workflows under one subscription.

Try Nomad AI →Launch Nomad Agent
What do you think?
Loading comments…