No. OpenAI and Anthropic each claim a 3-SAT algorithm that runs in subexponential time, which would refute the Exponential Time Hypothesis, but subexponential is still far slower than polynomial, so P vs NP stays open and the Clay prize is unclaimed.
This is the slow version of that answer: what P and NP mean, where 3-SAT sits, and why the late October 2026 results land one rung below the famous question. For dates and lab-by-lab detail, read my full news analysis of the ETH claims.
What is P vs NP, in plain words?
P vs NP asks whether every problem whose solution is easy to check is also easy to solve. Cook and Levin formulated it independently in 1971, and the Clay Mathematics Institute lists it among its Millennium Prize Problems.
Take a sudoku. A filled grid takes a minute to confirm, while filling an empty one means guessing and backtracking. A university exam timetable works the same way. Checking a proposed one for clashes is quick, and building one from scratch for thousands of students is far harder.
Clay’s own example is about housing. You must pick 100 students out of 400 applicants, and some pairs cannot be placed together. Checking a proposed list is quick. Trying every possible group of 100 is hopeless, because there are astronomically many.
In complexity theory, “easy” means polynomial time. If the input has size n, a polynomial-time method takes roughly n2 or n3 steps, or n to some other fixed power. That gives two classes:
- P holds problems you can solve in polynomial time.
- NP holds problems where a proposed answer can be checked in polynomial time.
Every problem in P is also in NP, since solving is a way of checking. The open question is whether the two classes are the same. Nobody has proved it either way.
What do NP-complete and 3-SAT mean?
Some problems in NP are as hard as anything in the class. Every NP problem can be translated into them efficiently, so solving one of them fast would solve all of NP fast. These are called NP-complete.
The textbook example is 3-SAT. You get a formula over n true or false variables. Each clause joins three variables (or their negations) with OR, and the clauses are joined with AND:
(x1 OR NOT x2 OR x3) AND (NOT x1 OR x2 OR x4)
Is there an assignment that makes the whole formula true? Checking a given assignment takes one pass over the clauses. Brute force means trying up to 2n combinations, which doubles with every extra variable.
Cook (1971) and Karp (1972) established that 3-SAT is NP-complete. That gives a clean test for the whole question: P = NP if and only if 3-SAT has a polynomial-time algorithm.
Before October 2026 the best known algorithms were still exponential, just with smaller bases. Anthropic’s paper cites O(1.328n) for deterministic algorithms (Liu, 2018) and O(1.308n) for randomized ones (the PPSZ line). The new results go further and count satisfying assignments, a variant written #3-SAT.
Did OpenAI or Anthropic prove P = NP?
No, and neither lab says it did. Both claim something narrower and still striking: 3-SAT can be solved in time 2o(n), meaning the exponent grows more slowly than any fixed multiple of n.
OpenAI’s post of 26 October 2026 says “our system has recently proved that the ETH is false, a result that was subsequently verified in Lean.” According to OpenAI, the AI found the disproof on 16 October and the Lean formalization followed on 17 October. Impagliazzo and Paturi of UCSD and Ryan Williams of MIT shepherded the work. OpenAI calls ETH “deeply related to the P vs. NP problem” and says practical improvements “will require significant further research.”
Anthropic’s paper, “A 2^{o(n)} Time Algorithm for 3-SAT”, lists its author as “Claude (Anthropic)” and is dated 26 October 2026. It says plainly: “our result does not bear on the P vs NP question directly, nor does it yield any practical algorithms for NP-complete problems.” The README adds that the result is “purely asymptotic and says nothing about solving formulas in practice.”
| Lab | What they claim | Stated running time | What it does not show |
|---|---|---|---|
| OpenAI (result 378, preprint “The Exponential Time Hypothesis is False”, dated 25 Oct 2026) | A deterministic algorithm that counts satisfying assignments of a k-CNF formula for every fixed k ≥ 2, in polynomial space. Also claims superlinear circuit lower bounds for a language in ENP | (n+m)O_k(1) · 2n / (log n)1/2 + o(1) | A polynomial-time algorithm, so no answer to P vs NP. No practical speedup yet |
| Anthropic (“A 2^{o(n)} Time Algorithm for 3-SAT”, dated 26 Oct 2026) | A deterministic algorithm that solves #3-SAT, checked in Lean 4 | 2O(n log log n / √(log n)) | Anything about P vs NP directly, or any practical algorithm for NP-complete problems, in the paper’s own words |
Both running times are subexponential, and both are very far from any polynomial. That gap is the whole story.
Why is ETH different from P vs NP?
The Exponential Time Hypothesis, from Impagliazzo and Paturi with Zane, says 3-SAT needs 2δn time for some constant δ > 0. That is a stronger bet than P ≠ NP, because it pins 3-SAT to the top rung of this ladder:
- Polynomial, like n3. This is the class P.
- Subexponential, like 2n / √(log n). Faster than any 2δn, slower than any polynomial.
- Exponential, like 2δn or 1.3n. This is where ETH said 3-SAT must live.
Take n = 1,000 and ignore constants. The polynomial n3 is one billion steps. The stand-in middle shape gives about 2316, roughly 1095. That beats 21000 by a mile and is still nothing a computer will ever finish.
The logic runs one way only. If P = NP, then 3-SAT is polynomial and ETH is false. But a false ETH does not make P = NP. The new results move 3-SAT from rung three to rung two. Getting it to rung one is the P vs NP question, and it is untouched.
Why would P = NP matter for crypto and AI?
Much of computer security rests on problems that are easy to check and believed hard to solve. A digital signature is quick to verify, and forging one is supposed to be infeasible. If P = NP came with an algorithm that is constructive and of low degree, many of those problems could become practical to solve.
The hedges matter. A proof could be nonconstructive, or its algorithm could need something like n100 steps, polynomial on paper and useless in practice. The October 2026 results are not even polynomial. Anthropic says its result yields no practical algorithms, and OpenAI says practical improvements need significant further research. Nothing here is a tool for breaking encryption.
For AI the link runs both ways. Planning and scheduling have the same check-easy, find-hard shape, so a practical P = NP algorithm would change what software can do. And this time AI systems produced the results. OpenAI says its system found the disproof, and Anthropic credits Claude as author. Trusting machine-made proofs is where Lean comes in.
What can Lean verify, and what can’t it?
Lean is a proof assistant. A small trusted program, the kernel, checks every step of a formal proof. If it accepts, the proof is correct relative to the formal statement.
Anthropic pinned Lean 4 v4.33.1 with Mathlib and ran a second kernel, nanoda, through a tool called Comparator, so two separate checkers accept the same proof. OpenAI says its disproof was formalized in Lean on 17 October, the day after its system found it, which falls in the week of my weekly for 12 to 18 October. OpenAI’s preprint is dated 25 October, the last day of the week the proofs landed.
What Lean cannot do is confirm that the formal statement means what the English paper claims. Anthropic’s README says so directly: “Lean checks the proofs, but no machine checks that this file says what the paper says.” A slightly wrong definition, or a theorem weaker than the headline, would pass the kernel. Lean also says nothing about whether a result is practical. More on these limits in my piece on OpenAI’s math results and Lean.
A Lean check is strong evidence the mathematics is sound as stated. Reading that statement against the paper is still a job for people.
Frequently asked questions
Is P vs NP solved?
No. The October 2026 results give subexponential algorithms for 3-SAT, which would refute the Exponential Time Hypothesis. Settling P vs NP needs a polynomial-time algorithm or a lower bound, and nobody has either.
Did Anthropic prove P = NP?
No. Anthropic’s paper says its “result does not bear on the P vs NP question directly.” It claims a deterministic 2o(n) algorithm for #3-SAT, which is subexponential, not polynomial.
What is the Exponential Time Hypothesis?
ETH, from Impagliazzo and Paturi with Zane, says 3-SAT needs time 2δn for some constant δ > 0. Refuting it shows 3-SAT can beat any true exponential, not that it can be solved in polynomial time.
Does a faster 3-SAT algorithm break encryption?
Not this one. The new bounds are subexponential and, per Anthropic’s paper, not practical. Even P = NP would only threaten cryptography if its algorithm were constructive and of low degree.
Is there a prize for solving P vs NP?
Yes. P vs NP is one of the Clay Mathematics Institute’s Millennium Prize Problems. Clay set aside US$1 million for the solution of each problem, and the P vs NP prize is still unclaimed.
Who first posed the P vs NP problem?
Cook and Levin formulated it independently in 1971. Karp’s 1972 work, alongside Cook’s, is the standard citation for 3-SAT being NP-complete.
1 comment