My friend asked: has P=NP been broken?
A friend sent me a news story and asked whether P=NP had fallen. The story is real, but it mixes up two things: it was ETH that was refuted, not P=NP. Here is the explanation I gave him.
On Tuesday night, a friend dropped a news screenshot into our group chat and asked: "Does this mean P=NP has been broken?"
I said: "It's not P=NP. It's ETH."
He asked: "Isn't that the same thing?"
At that moment I didn't have a good answer. We met for lunch the next day, and I spent half an hour walking him through it. This is what I said, plus the details I filled in later from reading the original manuscripts.
What actually happened
On October 6, OpenAI put several hundred mathematical manuscripts on GitHub. On October 26 it added two more. One of them is catalogue entry 378: 〈Disproof of the Exponential Time Hypothesis〉 — the paper's own title is 〈The Exponential Time Hypothesis is False〉.
The repository now holds 721 manuscripts across 373 families. The family numbers skip around, so "number 378" does not mean there are 378 families.
The same day, Anthropic said its model had found the core idea independently on October 16, and described OpenAI's model as having "independently and concurrently" proven a similar result.
My friend cut in: "So who got there first?"
"I don't know, and it doesn't matter." What matters, I told him, is that these are not papers yet.
OpenAI says so itself in the README: these are "raw research data, rather than polished academic papers", and "some of the unformalized results could have issues". About 42% of the top-line results in the repository have Lean formalizations; entry 378 is one of them, and its core time bound has been machine-checked.
The academic response was not slow. Impagliazzo and Paturi (who formulated ETH in 1999; journal version 2001) and MIT's Ryan Williams formed a working group and published an open letter. They stressed one thing: involvement is not certification.
As of October 28, MathWorld records that no independent verification had been reported.
Start with Sudoku
To explain this properly, we have to start with something that looks unrelated: Sudoku.
My friend nodded. He plays Sudoku.
"Imagine a filled-in grid. I show it to you, and you can check it in about ten seconds. Now imagine an empty grid. Finding that solution might take you half an hour."
That is the difference between P and NP. P is the class of problems you can solve quickly. NP is the class you can verify quickly.
And P = NP means: every answer you can verify quickly, you can also find quickly.
Almost everyone believes that is false, but nobody has proven it.
ETH is a stronger claim. It does not just say "3SAT is not in P". It says: there is a constant c such that 3SAT requires at least 2 to the cn steps. 3SAT is the most standard problem in that family — like Sudoku, it is NP-complete.
Here is an analogy. P ≠ NP only says "these two are not in the same place". ETH says "they are at least two thousand kilometers apart" — much more information.
Why would anyone assume such a thing
"What's the use of assuming something nobody has proven?" my friend asked.
The use is this: if you know two places are at least two thousand kilometers apart, you can rule out anyone driving there in an hour. A lower bound on distance eliminates an entire class of "fast" solutions.
That is how fine-grained complexity has worked for the past twenty years: assume ETH, then prove "if this problem had a fast algorithm, 3SAT would too, contradiction". So ETH is not a textbook term. It is the foundation under a whole shelf of papers.
What did OpenAI actually do
Their model found an algorithm that counts the satisfying assignments of a logical formula — counting them, not just deciding whether one exists, which is a stronger requirement. The running time is 2 to the n divided by the square root of the natural log of n, using polynomial space.
My friend pointed at the expression I had scribbled on a piece of paper: "What does that mean?"
"It means the exponent is still there, but divided by a number that grows slowly. The bigger n is, the more it gets divided."
"So it's faster?"
"It is. But faster than what?"
The best known 3SAT algorithm runs in roughly 1.307 to the n.
Take n = 1,000. That algorithm takes about 2 to the 386. This new one takes about 2 to the 380.
It is only about 60 times faster.
Sixty times sounds like a lot, until you notice that 2 to the 380 is still 10 to the 114. The age of the universe in seconds is only 4 × 10 to the 17.
The real difference appears when n gets large. Take n = 1,000,000: one is 2 to the 269,000, the other is 2 to the 386,000. The gap widens, but both remain astronomical.
So the point here is not "how much faster". It is "faster than that lower bound".
Keep upper and lower bounds straight
This is where people get confused.
An algorithm is an upper bound: it tells you the most time you need to get something done.
ETH is a lower bound: it says the least time anything must take.
This result pushes the upper bound down to sub-exponential. For large enough n, that upper bound falls below the lower bound ETH claimed — so ETH is refuted.
My friend asked: "Does that work in reverse too?"
"There are two kinds of 'reverse'."
P = NP would indeed imply ETH is false — but that is just the contrapositive of the same arrow, not a new deduction.
What does not hold is the other reverse: from "ETH has been refuted" you cannot conclude "P = NP". That arrow fails.
Back to the distance analogy: everyone thought it was at least two thousand kilometers; now someone proves it is only eight hundred. The distance got shorter, but your car is still too slow to arrive within an hour.
So whether P equals NP remains completely open today.
Then why does it matter
"If P = NP is untouched, why is everyone excited?"
"Because it knocks out a lot of intuitions."
Ryan Williams told reporters that some parts of the proof are, you might say, routine — but there are two or three "alien-looking" parts, and those are exactly what make this something the whole community needs to work through.
He also said something honest: "Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one's weight may vary."
"So has anyone checked it?" my friend asked.
"Yes, but they are not done."
About 42% of the top-line results carry Lean formalizations. Lean is a tool that lets a computer check a proof step by step. But a machine check is not the same as the result being true — it confirms the derivation has no gaps, not that the statement is the one everyone cares about, and not that the theorem is useful.
Three practical effects.
First, fine-grained complexity has papers to re-read. Those "assuming ETH, problem X cannot be solved below Y" conditionals lost their premise. The conclusions are not necessarily false, but they can no longer be used to derive unconditional lower bounds.
Second, cryptography is not broken. Today's systems rely on specific problems — factoring, discrete logarithms, lattices — not on the 3SAT family; and this algorithm is still exponential.
Third, engineering feels nothing in the short term. Anyone telling you this means "AI inference is about to get faster" is confusing a theoretical bound with a wall-clock time.
Back to the group chat
After lunch the next day, my friend asked one last question: "So is it fake news?"
"No," I said. "There is something real in it. What's wrong is turning it into 'P=NP has fallen'."
"How should I read stories like this in the future?"
I held up three fingers.
"First, is it a claim or a proof? A manuscript on GitHub is not the same class of object as a journal paper — especially when OpenAI itself writes 'this is raw research data'.
Second, how far did the formalization go? Lean can check a derivation, but it cannot guarantee the problem is the one everyone thinks it is.
Third, what does it refute, and what does it not? This refutes the claim that 3SAT requires at least 2 to the cn steps. It does not refute P ≠ NP, and it does not hand anyone a usable algorithm."
He put his phone away and said: "So the headline turned 'not that far' into 'we're there'."
Yes. That is exactly it.
Written on 2026-10-29, while academic review is still in progress. If independent verification appears, or the proof is found to have problems, I will come back and update this. The source material is family 378 in openai/math; the definition of ETH and its implications are on MathWorld.