If this holds up, it is one of the larger results AI has contributed to theoretical computer science. On October 6, 2026, posts on X and aggregator headlines said an algorithm found by Anthropic's Claude refutes the 3SUM conjecture and two companion hypotheses, and that a Lean formalization accompanies the paper.
Here is the important caveat, up front: we could not find independent expert review of the result. Everything below is "reported," not "established." This post explains what the claim is, why these hypotheses matter, what has to happen before anyone should say a conjecture "was disproved," and what builders should and should not take from it.
TL;DR: the questions people are asking
| Question | Short answer |
|---|---|
| What is claimed? | A Claude-found algorithm runs in n^(2-epsilon) time for 3SUM and APSP. |
| Which hypotheses fall? | Randomized Integer Word-RAM 3SUM, APSP, and Exact Triangle (as claimed). |
| Is there a formal proof? | A Lean formalization is reported. |
| Is it independently verified? | Not that we could find. |
| Who certified it? | Reports say an internal Anthropic research model, after the authors' draft. |
| Does it speed up real code? | Unlikely soon; such algorithms often have huge constants. |
| How to cite it? | "Reportedly," until outside experts confirm. |
What 3SUM and APSP are, in plain terms
3SUM. Given n numbers, do any three add up to zero? The obvious method checks pairs and looks up the third number, taking roughly n squared steps. For decades nobody found a truly faster general method, and the 3SUM conjecture says none exists: no algorithm in n to the 2 minus epsilon time for any epsilon above zero. The version in the claim is the Randomized Integer Word-RAM form, which fixes the machine model and allows randomness.
All-pairs shortest paths (APSP). Given a weighted graph with n nodes, find the shortest path between every pair. Classic methods take about n cubed time, and the APSP hypothesis says no truly subcubic algorithm exists for the general case. The claim is that one does.
Exact Triangle. Find a triangle in a weighted graph whose edge weights sum to zero. It is related to both problems.
Why these matter: they are anchors of fine-grained complexity. Researchers show that many other problems, in geometry, strings, graphs and dynamic data structures, are as hard as 3SUM or APSP. Those results are conditional: "if 3SUM needs quadratic time, this problem needs quadratic time too." If the anchor hypothesis is false, a whole web of conditional lower bounds loses its footing, and some of those problems may admit faster algorithms.
What is being reported
The coverage, based on three posts on X dated October 6 and a competitive-programming community blog post, says:
- Claude discovered an algorithm that refutes the 3SUM, APSP and Exact Triangle hypotheses.
- It resolves APSP in truly subcubic time.
- A paper and a Lean formalization accompany it.
- Anthropic used an internal research model to certify the main results after the human authors finished the first draft, and provided academic experts with compensation and access to Claude to help with the write-up.
One aggregator notes that the problems are described as important open problems "by some LLM-based rankings." That phrase is a reminder that "important" in a headline can come from an informal source, though 3SUM and APSP are genuinely central in the field.
We have not been able to read the paper ourselves or confirm details such as the exact epsilon, the constants, or the precise machine model. We also cannot tell how much of the discovery was the model's and how much was human framing. Those are the questions the paper and its reviewers will answer.
Why a Lean formalization helps, and what it does not do
We have written before about how formal proof checking has become much cheaper. A Lean file is machine-checked, so it removes one kind of doubt: that a step in the argument is wrong. If the file compiles against a standard library, each step follows.
Three kinds of doubt remain.
- Statement fidelity. Does the formal statement match the conjecture as the field means it? Subtle differences in the computational model, such as word size, how input numbers are bounded, or what randomness is allowed, can make a formal theorem weaker than the claim in the abstract.
- Algorithm correctness and runtime. Formalizing the algorithm's correctness and its running time bound is harder than proving a combinatorial lemma. Check what exactly was formalized.
- Novelty and context. Experts need to confirm the result is new and consistent with known barriers, and whether earlier work already implied something similar.
This is why our standing advice, repeated in our checklist for judging a mass release of AI math and in AGMAI's release rules, is to ask for the certificate, the statement and independent review, in that order.
How this fits the pattern of AI math claims
Over the past months, several labs have made mathematical claims, with different levels of evidence. Anthropic's earlier work included a Lean-formalized proof effort around Fermat's Last Theorem, and Claude-driven agents were reported to have found magnetic semiconductor candidates, which is science rather than mathematics. OpenAI's disputed claims, such as the Navier-Stokes result, taught readers to separate "announced" from "reviewed." The structure of this 3SUM claim is stronger than most: a formal artifact exists, academics were involved, and the claim is specific. It is still a claim until reviewers weigh in.
There is also a social angle we covered in are labs hoarding solved problems: the incentives to announce quickly are strong, and the review process is slow. A result that survives scrutiny will be remembered. One that has a flaw in the statement will be corrected publicly.
What to watch over the next weeks
- The paper itself, ideally on arXiv, with the full Lean repository.
- Statements from known complexity theorists, especially those who work on fine-grained complexity and have previously studied these hypotheses.
- Independent compilation of the Lean files, and checks by people who did not write them.
- The algorithm's constants. A truly faster algorithm in the asymptotic sense can still be impractical.
- Consequences. Which conditional lower bounds are affected, and which new algorithms follow for related problems.
- Anthropic's own account of how Claude was used, what the human authors contributed and what the certification step involved.
What a confirmed result would and would not change
Suppose the claim survives review. The immediate effect is theoretical. Conditional lower bounds that assumed 3SUM or APSP is hard would need re-examination, and researchers would look for which of them still stand on other hypotheses. Some problems that were believed to need quadratic time might admit faster methods, but only if the new technique transfers, which is not guaranteed.
The practical effect is slower and uncertain. Asymptotic improvements of the form n to the 2 minus epsilon are often tiny in exponent and heavy in constants, so they beat the classic method only for enormous inputs. History has several such algorithms that mattered enormously for theory and almost nothing for production code. A confirmed result would still be significant evidence about what AI systems can contribute to research mathematics, because the target was a problem that skilled humans failed to crack for decades.
If the claim fails, the likely reasons are mundane: a statement that is weaker than the conjecture, a model-of-computation detail, or a subtle gap in how runtime was formalized. Those outcomes would still teach the field something about how to review machine-generated proofs.
What this means for builders and learners
If you build software, nothing in your stack changes today. Do not expect faster shortest-path libraries next month, and be skeptical of anyone who says so. For the long run, a confirmed subcubic APSP would eventually motivate new algorithms in routing, graph analytics and bioinformatics, but that is a research timeline, not a release cycle.
If you teach or write about AI, the useful lesson is about language. Compare "an AI disproved a famous conjecture," which is a headline, with "a formalized claim, reported by several outlets, awaiting expert review," which is the status. The second sentence is less exciting and more accurate. The same discipline applies to any AI claim: ask what artifact exists, who checked it, and what remains unverified.
If you are curious how language models do mathematics at all, our explainer on how language models solve math and disease is a good place to start.
Related reading
- Claude and Fermat's Last Theorem: the Lean proof effort
- Lean 4 and the collapse in formal proof cost
- OpenAI's "400 math papers" rumor and how to check a mass release
- AGMAI's rules for releasing AI math
- Are AI labs hoarding solved math problems?
- No, AI didn't just solve Navier-Stokes
- Claude Opus 5.5 agents and magnetic semiconductor candidates
- How language models solve math and disease
Primary: posts on X dated October 6, 2026 and a Codeforces community blog entry reporting the result · aggregator coverage (HuggingNews). The paper and Lean repository should be read directly once linked.
This post reflects what was public on October 6, 2026. The result is claimed and not independently verified, and details such as the exact bounds were not confirmed by us. We will update it as expert review appears.