Lance Fortnow has blogged about computational complexity for more than two decades, and he is not given to gasping. His post on the new claim ended with a careful sentence: "I have not verified the proof myself, but it is safe to assume now that the exponential-time hypothesis is toast" (Computational Complexity).
The claim comes from two labs. OpenAI, the company behind ChatGPT, says its model refuted the Exponential Time Hypothesis, usually shortened to ETH. Hours later Anthropic, maker of Claude (the two assistants are compared here), published its own refutation. Headlines then tied the news to a fight among mathematicians and to fears for global encryption. We read both labs' own write-ups, the expert commentary and the news coverage, and our view is plain: the result is probably real and important to theorists, and it is not a reason to change how you protect your data. Two of the three headlines concern different disputes, and the third is about a trend.
What is the Exponential Time Hypothesis, in plain terms?
Start with a puzzle called 3-SAT. You get a long list of conditions over n true-or-false switches, each condition shaped like "A, or not B, or C", and you must find a setting of the switches that satisfies every one. Checking a proposed setting is quick. Finding one is the hard part, much like a Sudoku, where a finished grid is easy to verify and a blank one is not.
ETH, proposed in 1999 by Russell Impagliazzo and Ramamohan Paturi (with Francis Zane), says every algorithm for 3-SAT needs time growing like 2 to the power of c times n, for some fixed c above zero (Fortnow). Picture a combination lock where each extra dial multiplies the work by a fixed factor, say 1.3. ETH says that factor can be shaved down but never to 1.
The refutation says the factor does shrink toward 1 as formulas grow. OpenAI's paper gives, per Fortnow, a running time of about 2 to the power of n times log log n over the square root of log n. That is still far from fast. It only grows more slowly than any fixed multiplier would. Anthropic's own write-up is blunt about it: "The result is purely asymptotic and says nothing about solving formulas in practice" (Anthropic).
Why did theorists care so much? ETH had been used in hundreds of papers as a stand-in for "this problem can't be solved much faster" (OpenAI). If the hypothesis is false, those hardness arguments need rechecking, though Fortnow notes that "the fact that ETH and SETH fail doesn't mean their implications are false."
More has been checked than usual, and less than settled
The checking so far is more than most breakthroughs get in a first week. OpenAI says its model found the disproof ten days before the announcement and that it was formalized in Lean, a proof checker that accepts only steps it can verify (OpenAI). Anthropic says an internal Claude model found its version, and its Lean files were written by AI models (Anthropic).
Humans have since joined in. Ryan O'Donnell of Carnegie Mellon posted a rewritten exposition of the proof, and Fortnow says Shiva Kintali posted another, both aiming for simplicity over the best bounds. Timothy Gowers called it "Very surprising and consequential that it is false" (Business Insider).
The people formally assigned to check it are Impagliazzo, Paturi and MIT's Ryan Williams, who told TechCrunch that parts of the proof are routine but that "there are two or three alien-looking parts". Business Insider reports Williams has not certified the result and that the group says its involvement is not an endorsement. One more caution from Anthropic's own repository: Lean checks the proofs, but "no machine checks that this file says what the paper says", so a person has to read the short statement file. They've kept it short for that reason.
Our read: a claim from two labs, machine-checked proofs and human rewrites in days is unusually strong. It is still a claim until the expert group and a journal say otherwise.
Is the mathematicians' fight about this result?
Mostly not. The BBC's "bust-up between mathematicians" is about a different problem. Its story covers the Navier-Stokes dispute, where NYU's Tristan Buckmaster asked whether his drafts, stored in OpenAI's Codex tool, could have fed OpenAI's own work. OpenAI said nobody there saw the other team's work, and that his prompts "could not have influenced the system in any way".
Scientific American's "scooped" headline is about Yang-Mills, a physics problem. The magazine says OpenAI appears to have beaten Ethan Sussman, working with Anthropic's Levent Alpöge, to a proof. Alpöge objected on X. None of that concerns whether the 3-SAT algorithm works.
The ETH quarrel is about process. Williams called an earlier OpenAI release "a DDOS attack on mathematicians" (X), then agreed to help with this one. Scientific American says OpenAI's approach to two of the three results violated a clarifying statement from its own expert advisory group on AI and mathematics, and that the prompts and chain-of-thought behind them are still private. For ETH, OpenAI did agree to publish the proof and fund a conference.
Does it break RSA or the encryption on my phone?
No, and not by this route. We'd put it that flatly because the reasons are specific. First, the algorithm solves k-SAT. Fortnow stresses it "gives nothing new for Subset Sum or Traveling Salesman", because turning those into 3-SAT inflates the number of variables too much. Second, RSA rests on the difficulty of splitting a huge number into two primes (the Financial Times describes the method without naming it), which is a different problem from satisfying logic formulas, and none of the sources we read says the new algorithm reaches it. Third, the bound is asymptotic: nothing about a 2,048-bit key changes on any machine that exists.
Williams raised the obvious worry with OpenAI's science lead, Dan Roberts. Per TechCrunch, he asked whether anything was insecure now, and relayed that, apparently, OpenAI had checked and was "reasonably confident" it implied no breaks. That is secondhand and unpublished, so weigh it accordingly. Williams also said an improved algorithm could imply that some key sizes count as broken.
There is a real open question underneath. Williams says "every computer scientist should probably put a little more weight on the plausibility of P = NP", but John D. Cook points out that "the status of P = NP is still unknown" (Business Insider). Williams doesn't think the new algorithm is the best possible either. If a sharper one arrives, the arguments change.
The Financial Times piece is about a trend, not this proof
The FT article is about AI's growing mathematical ability and encryption in general, and in the text we could read it never mentions ETH. Its sources are measured. Australian mathematician Geordie Williamson told an Imperial College audience that AI is causing "a complete kind of restructuring of what difficulty is", and that we should expect shocks. Daniel Shiu of the University of Manchester called AI cracking encryption a "significant risk" for "more mathematical forms of cryptography", naming some of the "less mature" quantum-resistant algorithms. The FT itself says AI "has yet to break a core cryptography method".
Scott Aaronson added a loose thread: cryptography is conspicuous by its absence from OpenAI's earlier list of 376 papers, and in an update to his post he wrote that his sources say AI companies have begun investigating whether their models can break protocols. He gave no names, and neither can we.
Our reading: the sensible worry is about newer schemes, not the ones in your browser. NIST's 2024 standards include two lattice-based schemes and a third signature standard built on a different kind of math, kept as a backup in case the first proves vulnerable.
What a small business should actually do
Almost nothing, and nothing urgent. The tree below sorts the three situations we think matter.
One habit is worth adopting regardless of this story. The UK's regulator told the FT that "firms shouldn't wait to act" on preparing for AI and quantum risks to cryptography, and BT said it wants its cryptography to be "changed more readily as standards, technologies and threats evolve". For a small shop that translates into keeping software updated and asking vendors how they'd swap algorithms. Our framework for trusting AI tools with your data covers the vendor questions, and ToolRank's Security & Privacy board lists tools by category.
Three things to watch before anyone says settled
Watch for three things. The expert group's write-up from Impagliazzo, Paturi and Williams, and the conference OpenAI agreed to fund. Independent readings of the Lean statement files, since that's where a subtle error could hide. And journal peer review, of which we found no sign yet. Until the first of those appears, we'd say "very probably refuted".
