Claim check · Last reviewed 31 Oct 2026
Did AI disprove the Exponential Time Hypothesis?
You may see videos and posts saying that AI has overturned a major complexity-theory result. That would be a very large claim. Before repeating it, we need a precise statement, a checkable proof and appropriate expert review.
The idea in plain language
What is the Exponential Time Hypothesis?
It is a proposed explanation for why some computational problems seem fundamentally hard. It is not the same as saying “no one has found a fast method yet”.
Simple version: certain hard logic problems may require time that grows exponentially with the size of the input.
More precise version: there is some fixed constant s > 0 such that 3-SAT cannot be solved in O(2sn) time for inputs with n variables.
Important: ETH is a hypothesis, not a proven theorem. A claim that AI “disproved” it therefore needs unusually strong evidence.
What would change the status
Three things would need to be visible.
A dramatic headline or a summary is not enough for a theorem-level claim. We would need to inspect the intellectual chain from statement to result.
- 01A precise mathematical statement.
What exactly is being disproved? Which version of ETH? What is the claimed algorithm, bound and scope?
- 02A checkable proof artifact.
Where is the paper, formal proof, code, proof term or complete argument? A demo or abstract is only a lead.
- 03Appropriate expert review or independent checking.
The formal statement must match the headline, and qualified people must have had a chance to inspect it.
Five-question checklist
Use this before believing any AI discovery headline.
These questions work for algorithm discoveries, automated proofs and complexity claims. They are designed to slow down a confident headline.
- 01What exactly is claimed?
Write the theorem or result as a precise statement, not a slogan.
- 02Where is the artifact?
Look for the paper, formal statement, code, proof term or dataset.
- 03What checks the result?
A proof assistant, independent reproduction or expert review is stronger than a demonstration.
- 04What is the scope?
Identify the task, assumptions, input sizes, hardware and baseline.
- 05What remains open?
Separate the established result from the wider interpretation in the headline.
Evidence labels
The four labels used across this site.
Unverified is a review status for a specific claim; it is not a type of evidence.
Published after scholarly peer review.
A concrete result or public artifact exists within a stated setting.
Credible experts or evidence point in different directions.
A forecast or interpretation not yet supported by direct evidence.
More evidence