Within a few hours on Oct. 26, OpenAI and Anthropic each published a machine-checked proof that 3-SAT, the logic puzzle at the root of much of complexity theory, can be solved faster than any exponential function of its size, a result that would refute the Exponential Time Hypothesis computer scientists have built on since 1999.
The two claims end up in nearly the same place. Each describes a deterministic algorithm that counts the solutions to a formula with n variables in roughly 2^(n/√log n) steps. The best algorithm published before this month needed about 1.307^n. Each comes with a formal proof in the Lean proof assistant. Nobody outside either company has yet confirmed either one.
Read closely, the record supports a narrower story than the headlines did. If the proofs hold, they also take down the stronger hypothesis known as SETH and knock out the stated premise of more than 800 papers, by Anthropic’s count. They do not show that P equals NP, OpenAI told reviewers it found no cryptographic system they break, and by one reading of Anthropic’s own paper the new method does not beat brute force until a formula has about 10^10,000 variables. The open question is less whether a computer checked a proof than whether the theorem it checked is the one the field meant. That job falls to a few unpaid academics, two of whom proposed the hypothesis in the first place.
What each lab claims
OpenAI’s paper is a 67-page preprint titled The Exponential Time Hypothesis Is False, signed only “OpenAI” and posted in the company’s public math repository. The company said an unnamed internal model found the argument on Oct. 16 and that the proof was formalized in Lean the next day. The manuscript is dated Oct. 17 and was revised Oct. 25. OpenAI announced it on Oct. 26 in a blog post, next to claimed results on the Kakeya conjecture and on four-dimensional quantum field theories, as The Next Web reported.
The algorithm handles any formula whose clauses each contain at most a fixed number k of variables, not just three. On a formula with n variables and m clauses it uses polynomial memory and runs in time (n+m)^O(1) × 2^(n/(log n)^(1/2+o(1))), according to the paper. It counts solutions instead of finding one, which is the harder task. A count of zero means the formula can’t be satisfied, so the same algorithm also decides 3-SAT.
Anthropic’s version, posted hours later, is credited to “Claude (Anthropic)” and titled A 2^o(n) Time Algorithm for 3-SAT. It was deposited on the preprint server Hexagon on Oct. 27, with a Lean 4 formalization in Anthropic’s formal-math repository. The paper says the core algorithm “was found on October 16 by an internal Claude research model with 14M output tokens and no human input,” and that company researchers then worked with the model on the write-up. The repository gives the counting bound as 2^O(n log log n/√log n), the same form as OpenAI’s general bound.
The two routes appear to differ. The repository condenses Anthropic’s idea into one paragraph about contracting tensor networks and says Claude Opus 5.5 at high effort can rederive a weaker form of the result from that paragraph alone. Jelani Nelson, who read Claude’s proof before release, said both proofs reach roughly exp(O(n/√log n)), TechTimes reported. Dr. Nelson, a theoretical computer scientist, is on leave from the University of California, Berkeley, to work at Anthropic. The mathematician and philosopher Samuel Allen Alexander has posted a reading of both papers.
How much faster
For most of 3-SAT’s history, progress meant shrinking the base of an exponent. Brute force checks all 2^n settings. In 1985 Burkhard Monien and Ewald Speckenmeyer gave a branching algorithm that runs in about 1.618^n steps, the golden ratio to the nth power, as the applied mathematician John D. Cook recounted on his blog. The PPSZ algorithm, named for Dr. Paturi and three co-authors, and its successors went further. In 2019 Thomas Dueholm Hansen, Haim Kaplan, Or Zamir and Uri Zwick brought the bound for formulas with a single solution to 1.307^n, which is about 2^(0.386n).
Every one of those bounds has the form c^n for some c greater than 1, and ETH says that form can’t be escaped. The new bounds divide the exponent by √log n, a factor that grows without limit but very slowly. Setting aside the constants hidden in the notation, a formula with a million variables gets its exponent cut by a factor of about 4.5, and one with a billion variables by about 5.5. No fixed c keeps up forever, so ETH falls. Nobody’s computer gets any faster.
The hidden constants are where the result stops being practical. TechTimes, reading Anthropic’s paper, reported that the crossover past brute force “requires roughly 10^10,000 variables.” That figure could not be independently verified. Anthropic’s repository says it outright: “The result is purely asymptotic and says nothing about solving formulas in practice.” OpenAI said that turning the theory into practical gains would take much more research, Decrypt reported.
On Hacker News, a reader who described himself as a SAT-solving expert answered another who asked whether the method had any immediate use.
SAT-solving expert here. No immediate applications (the results in the paper are “galactic”). The main question is whether some ideas here will snowball into other ideas, one of which could eventually be very practical.
Both labs’ caveats back the first half of that answer, and the second half has a recent precedent. Earlier this month, after Josh Alman and Virginia Vassilevska Williams posted a faster algorithm for a problem called 3SUM, Sankeerth Rao Karingula and Shachar Lovett posted a simpler proof six days later, with weaker exponents. Something similar started within hours this time. On Oct. 26 Shiva Kintali posted a simplified proof that solves 3-SAT in time proportional to 2^(εn) for every fixed ε greater than zero, Dr. Cook wrote. That is a weaker statement than either lab’s bound, and it is still enough to refute the standard form of ETH.
A hypothesis from 1999
Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego, stated the hypothesis in 1999 in a paper called “The Complexity of k-SAT.” In 2001, with Francis Zane, they supplied the tool that made it useful, according to the history of the conjecture. Their sparsification lemma showed that a subexponential algorithm for 3-SAT would give one for every k-SAT. After that the hypothesis became a standard starting point for lower bounds. Assume it, and graph coloring, Hamiltonian cycle, independent set and vertex cover have no subexponential algorithms, and a clique of k vertices can’t be found in time n^o(k). In 2009 Dr. Impagliazzo, Dr. Paturi and Chris Calabro were credited with SETH, which says that as clauses get wider, the best algorithms for k-SAT come ever closer to brute force.
Even its authors held it loosely. In a 2012 lecture, Dr. Impagliazzo said of ETH and SETH that “it’s about a fair coin flip whether they’re true or not,” according to the same history. Ryan Williams, now a professor at the Massachusetts Institute of Technology, went further. In 2015 Arturs Backurs and Piotr Indyk of M.I.T. proved that edit distance, the standard measure of how far apart two strings are, can’t be computed in strongly subquadratic time unless SETH is false. Dr. Williams then told Quanta Magazine that he doubted the premise.
It is a hypothesis, and I don’t believe it’s true.
Business Insider wrote this week that Dr. Williams has previously said he doesn’t believe in ETH. His on-record doubts were mostly about the stronger hypothesis. In a paper estimating the likelihood of open conjectures, he put SETH’s chance of being true at 25 percent and ETH’s at 70 percent. The labs say they broke the one he thought more likely.
What falls with it
SETH goes too. It is the stronger claim, so whatever refutes ETH refutes it as well, and OpenAI’s paper says its theorem also disposes of two variants, Gap-ETH and NSETH. Anthropic said a literature search by Claude found more than 800 papers that prove at least one result only under ETH or a hypothesis implying it, TechTimes reported. OpenAI’s post put the number at hundreds, across graph theory, computational biology, databases and geometry. Dr. Williams told TechCrunch that many papers from the past decade would need to be revisited if the result holds.
Revisited is not the same as wrong. A theorem proved under ETH becomes a statement with a false premise, but many such results can be re-derived from weaker assumptions. Most of the quadratic lower bounds called SETH-based, including Backurs and Indyk’s for edit distance and similar ones for longest common subsequence and Fréchet distance, actually go through the Orthogonal Vectors problem, according to the standard summary of the field. SETH implies the Orthogonal Vectors hypothesis, not the reverse. Those bounds can rest on that hypothesis instead, and nobody has claimed to refute it.
That fallback matters more than usual this month. On Oct. 5 Dr. Alman and Dr. Vassilevska Williams posted algorithms that run in O(n^1.9992) time for 3SUM and O(n^2.9995) for all-pairs shortest paths, and wrote that the result refutes the 3SUM and APSP hypotheses, the field’s other two standard assumptions. Scott Aaronson, a complexity theorist at the University of Texas at Austin, wrote on his blog that an Anthropic model, not an OpenAI one, supplied the central idea, and that the paper itself says SETH was unaffected. Within three weeks, all three of fine-grained complexity’s standard hypotheses have been claimed false. Orthogonal Vectors is the best-known one still open.
The hypotheses reach into machine learning too. On Hacker News, one reader pointed to a 2022 paper proving that self-attention, the core operation in large language models, needs quadratic time unless SETH is false, and asked what follows.
If OpenAI’s proof is correct, does that mean self-attention can be implemented in sub-quadratic time? I.e. we could eventually have all the most advanced LLMs running on cheap hardware? To put it more playfully, is ETH being false actually bearish for Nvidia?
Another reader answered that the question was “not even wrong,” and the logic is on that reader’s side. A conditional lower bound whose premise fails says nothing either way. It doesn’t hand anyone a faster algorithm. If that paper’s reduction runs through Orthogonal Vectors, as most SETH-based bounds do, the quadratic bound survives on that footing. A speedup that starts somewhere near 10^10,000 variables wouldn’t touch any input a real model will see.
Nor does the result say much about P versus NP. ETH implies P ≠ NP, but its failure doesn’t imply the reverse. OpenAI’s paper states that “runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions,” so the result “does not imply that general NP problems admit subexponential time algorithms.” The speedup does carry over to problems that reduce to 3-SAT with only a linear number of variables, and the paper lists counting independent sets, proper colorings and perfect matchings. Dr. Cook put the bottom line in his post.
While 3-SAT does not take exponential time, it still takes more than polynomial time as far as anyone knows.
Dr. Williams allowed for a modest shift. “Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one’s weight may vary,” he told TechCrunch. On Hacker News, a reader recalled that Donald Knuth has long stood almost alone on that question.
someone like Knuth has always seemed a bit of an outlier for saying that maybe P=NP: his argument was simply that there are so many possible polynomial-time algorithms that we haven’t explored, and maybe one of them with a large exponent could solve NP-complete problems.
The cryptography question
Dr. Williams said an improved algorithm of this kind could in principle mean that cryptographic systems relying on certain key sizes count as broken. One of his first questions to Dan Roberts, OpenAI’s science lead, was whether anything was now insecure. “Apparently, they checked, and they were reasonably confident that this didn’t ... imply any breaks,” he told TechCrunch. The company that made the claim ran that check itself.
Some readers didn’t take that on trust. On Hacker News, one argued that concentrating the world’s mathematical talent inside A.I. labs creates a disclosure problem.
Part of the problem with the current centralization of the world’s math capability within AI labs is that if they do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography. So it’s not completely clear that they will (be allowed to) release these results.
On this result the math points toward reassurance. Public-key systems in use rest on particular problems such as factoring, not on worst-case 3-SAT, and as another reader noted, those problems have no proven exponential lower bound to lose. OpenAI’s own caveat about reductions closes the indirect route, because a subexponential bound doesn’t survive the blowup in variables that translating other problems into 3-SAT usually causes. A cipher written as a 3-SAT formula gets a variable for every internal wire of its circuit, not just its 128 or 256 key bits, so a 2^(n/√log n) search over all of them is far slower than simply trying every key. And the crossover sits near 10^10,000 variables.
The suppression theory has less behind it. Nothing in the record shows any government asking to see or hold back a result. The reviewers signed no nondisclosure agreements, and Dr. Williams wrote on X that OpenAI agreed to release its raw data and sponsor a conference. A reader replying in the same thread called the veto theory unfair and said that real security findings are usually held back for coordinated disclosure, not buried.
Who checks a machine proof
A Lean proof either compiles or it doesn’t. Anthropic’s proof depends only on Lean’s three standard axioms, according to its repository, which also re-checks every declaration with a second, independent kernel called nanoda. What Lean can’t check is whether the formal statement says what the English one does. OpenAI’s Lean theorem proves a slightly weaker bound than its paper, with (log log n)^2 in the exponent where the paper has log log n, Popular AI noted. Either one would refute ETH. Anthropic’s repository states the general limit.
Lean checks the proofs, but no machine checks that this file says what the paper says; the file is kept short so that a reader can check this.
That leaves a human job, smaller than refereeing a 67-page paper but not trivial. The build is open to anyone: Anthropic says it takes about eight minutes on 24 virtual CPUs, with peak memory around 7 gigabytes. The statement file is short. A reader still has to confirm that its Turing machine model, its encoding of formulas and its measure of running time match what complexity theorists mean by solving 3-SAT.
On Hacker News, one reader who said he had an OpenAI model walk him through the Lean code described OpenAI’s construction as two halves: small inputs answered from an enormous precomputed table, large ones by an algebraic method. He rejected the result.
I’m not inclined to consider “wrote down all the answers ahead of time, so that’s free” as a quadratic time solution to SAT. Nor very convinced by the other half.
He said his description came secondhand from a model, and it could not be checked against the paper. Even taken at face value, a table for small inputs doesn’t by itself sink an asymptotic claim. ETH is about how running time grows, and complexity bounds ignore any finite set of inputs. The objection with teeth is the other half: whether the method for large inputs works and whether the formal model of computation is an honest one. That is the check the review group has set for itself.
The referees
OpenAI didn’t leave the checking to Lean alone. Before the release it asked Dr. Williams, Dr. Impagliazzo and Dr. Paturi to organize an open examination, and Dr. Williams announced the arrangement on X.
An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim. 1/4
The three signed no nondisclosure agreements and aren’t being paid, Dr. Williams wrote. They asked OpenAI to release all its raw data on the result, PDFs and Lean source included, and the company agreed. Their open letter is plain about what their names mean: “Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny.” Dr. Paturi told The Washington Times that his first reaction was surprise and that “if it holds up, it would be a major advance in our understanding of the limits of computation.”
The letter also warns that credit may flow to whoever publishes first or has the strongest tools, while the work of verifying and explaining goes undervalued. OpenAI says it wants no academic credit for the result. It has given $5 million to the Simons Foundation for workshops and conferences on A.I.-produced results. The arrangement follows a release Dr. Williams disliked: earlier this month OpenAI posted hundreds of mathematics manuscripts at once, which he called a “DDOS attack on mathematicians.” This time each field got different handling. The mathematicians got their proof on GitHub, the computer scientists a working group and a conference, and the physicists formed a group that will decide how their result is released. OpenAI’s own Advisory Group on Mathematics and AI has urged immediate publication of the physics proofs, R&D World reported. Dr. Williams told TechCrunch what made him take on the work.
Some parts [of OpenAI’s proof] are, maybe you could say routine, but then yes, there are two or three alien-looking parts, and it’s exactly these parts that I saw that made me think, wow, this is something that the whole community needs to work on together
Human readers have moved fast. The simplified proof posted on Oct. 26 says it proves its main theorem without relying on the new lemmas in OpenAI’s paper. A Hacker News reader reported that Dr. Williams’s thread links to a shared folder holding both labs’ papers and a new, readable human contribution from Amit Sahai, a cryptographer at the University of California, Los Angeles. That paper could not be independently verified.
Two labs, one day
Both companies date their discoveries to Oct. 16. Levent Alpöge, a mathematician at Anthropic, suggested that OpenAI’s solutions drew on pre-existing work, TechCrunch reported, and hours later Anthropic posted its own. Anthropic’s paper acknowledges the rival in one line: “Independently and concurrently, an internal model at OpenAI claims to have proven a similar result.” The labs also release A.I. mathematics differently. Dr. Aaronson wrote that OpenAI’s way “sets up a crazy race among humans to digest and explain a messy AI proof.” Anthropic’s way, used for 3SUM, has a private firm choosing which mathematicians present the result: it paid Dr. Alman and Dr. Vassilevska Williams to extend and write it up. Dr. Aaronson didn’t pick a side.
Reaction came within hours. Timothy Gowers, a Fields medalist at the Collège de France, quote-posted Dr. Williams’s announcement. Dr. Aaronson noted the news at the end of an unrelated post, describing an algorithm whose time “scales roughly like exp(n/√log(n)).”
For those who don’t know, ETH is the hypothesis that 3SAT needs exponential time. Very surprising and consequential that it is false.
Gary Marcus, an emeritus professor at New York University who is usually skeptical of A.I. claims, called it “a big deal if correct” on X, according to Business Insider. Joshua Fonseca Rivera, an A.I. safety research fellow at Anthropic, wrote that “the bitter lesson should make this unsurprising,” then added: “I know this logically, but... wow, we really don’t know anything.”
What comes next
The organizers have set up a discussion blog, a shared repository for notes and corrections, and a form where researchers can volunteer. Their plan covers checking the proof independently, making it understandable through explanations, simpler proofs and seminars, and studying the consequences while keeping established conclusions apart from speculation. OpenAI’s conference and the Simons Foundation workshops come later. Dr. Williams expects better algorithms to follow. “I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get,” he told TechCrunch.
The letter proposes a virtual meeting for the research community “before the end of 2026.” As of Wednesday, no date had been set.