p.enthalabs

Three new discoveries in mathematics, computer science, and physics

1,076 points · 83 visible top comments · 2026-10-26 21:35:28 UTC

openai.com · Read Story HN original

Related:

The Exponential Time Hypothesis Is False [pdf] - https://news.ycombinator.com/item?id=50251661

Comments

rbranson · 2026-10-26 21:40:19 UTC
The title buries the lede quite a bit:

> The Exponential Time Hypothesis is false

JonChesterfield · 2026-10-26 21:58:52 UTC
by fucking sorry written at the end of the proof
JonChesterfield · 2026-10-26 22:24:02 UTC
awesome, thanks!
sebzim4500 · 2026-10-26 22:26:11 UTC
They do that to make it easier for readers to verify the statement (which is entirely contained in that file) separately from the proof (which is spread over thousands of files and github can't even show them all).

Proof is at https://github.com/openai/math/tree/main/lean/OAI/Algorithms...

Sniffnoy · 2026-10-26 21:56:33 UTC
This is just one of the three ledes, really!
eluru · 2026-10-27 07:09:36 UTC
sadly the only one they kind of explain, open AI is mysterious and cold like sasuke
yu3zhou4 · 2026-10-26 22:14:13 UTC
A newbie here, does it mean that SETH is false too?
pavitheran · 2026-10-26 22:17:22 UTC
Yes it means both SETH and ETH are false.
Loughla · 2026-10-27 01:24:13 UTC
This is so far above my head it isn't even funny. I just looked up ETH and was 9 links in before I realized even the explanations of the parts of it were out of my grasp. Can someone explain the implications of this?
kingstnap · 2026-10-27 04:26:37 UTC
It depends on your background. If you don't have a computer science background the statement needs layers and layers of buildup that can't happen in a single hacknews comment. But the outside implication is still accessible.

The outside implication for what is going on is that OpenAI has very clearly demonstrated insane capability in coming up with clever algorithms. You cannot deny some real level of super human like abstract reasoning here.

K-sat is the hard theoretical computer science problem. Nothing else is close in terms of how much it has been studied. There are journals and conferences for SAT.

It is really hard to come up with faster ways to solve it. So much so that people were convinced that you really can't go faster than exponential time. OpenAI has just shown a breakthrough construction better then decades of research by elite specialists was able to come up with.

baq · 2026-10-26 22:46:16 UTC
What a time to be alive honestly. Can’t know what one will wake up to
adverbly · 2026-10-26 23:19:24 UTC
> superpolynomial

I've got some reading to do it seems...

QuesnayJr · 2026-10-27 06:38:36 UTC
Polynomial is something like exp(n log x), where x is the problem size. Exponential is something like exp(x). Superpolynomial but subexponential is roughly when the exponent is between n log x and x. An exponent of (log x)^2 would do the trick.

The actual exponent OpenAI found was x/sqrt(x).

pfdietz · 2026-10-27 12:50:23 UTC
x/sqrt(log(x)), I believe.
mFixman · 2026-10-27 08:47:34 UTC
I assumed all new breakthroughs in advanced complexity theory would be theoretical and non-constructive, as in "we prove that this algorithm must exist but we do not provide it".

I'm genuinely shook at today's results, specially at the fact that there _is_ a constructive algorithm.

mlinsey · 2026-10-26 21:51:48 UTC
I understand that the Exponential Time Hypothesis being false doesn't necessarily mean P=NP, but for people who are a lot more knowledgeable about complexity theory, does this update your priors significantly in the direction of P=NP?
novaRom · 2026-10-26 22:51:29 UTC
For me, this result is significant. It basically adds much more hope P is equal NP (that majority seems being against). I believe one day AI will explain a major flaw in modern mathematics, so a kind of correction in axioms will be suggested to prove Rieman's hypothesis (or a completely new apparatus)
rcpt · 2026-10-26 23:00:21 UTC
I don't know if that's a "flaw". It's what Godel Incompleteness guarantees.

Would be funny if the most famous problem turns out be an example though

skew-aberration · 2026-10-26 23:12:19 UTC
That's not that how that works btw. The incompleteness is a property of the algorithm which does the proofs, not the theorems. If a theorem is true it has a proof and a program which proves it (printf("the proof verbatim")). But no computer program can successfully prove all theorems. The space of potential proofs is too big to search systematically, but you can still get lucky.
rcpt · 2026-10-26 23:43:22 UTC
Godel says that there are statements that are true but have no proof within that system. It's not about algorithms.

I'm saying it'd be funny if Riemann were true but not proveable.

Though I guess it's actually funnier. If Riemann were false then there would be a counterexample, so it's clearly within existing axioms.

So if one can prove that Riemann isn't proveable in our current axioms then it has to be true.

plagiarist · 2026-10-27 00:32:13 UTC
Can something be both true and unprovable without being a self-referential Godel sentence? I assume most statements that aren't self-referential are independent, like the continuum hypothesis with ZFC.
skew-aberration · 2026-10-27 00:57:22 UTC
Godel sentences are only true if you assume consistency. And once you add that axiom, the computer can prove them too.

G is independent of your original system T (cannot be proven true or false).

If you create T+ with added consistency axiom, then G is true and provable.

But G is never true and unprovable in the same system.

It's a lot like is/ought or theology.

noslenwerdna · 2026-10-26 23:54:58 UTC
That is also not how it works. The theorem says that there exist some true statements for which there is no proof. This is assuming the axioms are consistent.
skew-aberration · 2026-10-27 00:21:07 UTC
I think you're right, I'm conflating two separate things.

EDIT: I am wrong (it's been a while) but there is nuance.

I said any computer program fails to prove some true statements. In fact, some 'true' statements cannot be proven by any program, as others have said.

But for those statements G, you can prove 'G is true if our system is consistent', just not 'G is true'.

So when we say G is 'true', we are really just asserting the consistency axiom that our computer program is denied.

_dain_ · 2026-10-26 23:46:05 UTC
Why do you "hope" P=NP? It would be a catastrophe
coliveira · 2026-10-27 00:10:05 UTC
Why? Nature doesn't care if people are making financial transactions based on flawed cryptography.
80fj0348i · 2026-10-27 01:19:13 UTC
Have you been in nature? It's cold and full of bugs and disease.
rcpt · 2026-10-27 00:17:30 UTC
Not really. P=NP but the degree of the polynomial is Grahams number doesn't let people into your bank account
andriy_koval · 2026-10-27 00:37:02 UTC
it could make lots of compute way more efficient, not sure why it is catastrophe..
jibalt · 2026-10-27 03:31:02 UTC
Either P=NP or not. Hoping one way or the other changes nothing. Nor does it change how efficient computing is, nor does it have any effect on cryptography. Discovering a vastly more efficient means of factoring primes--perhaps via quantum computing--would do that. But just learning that P=NP does nothing to further such a discovery. Almost certainly, if P=NP, the exponents and/or constants in a polynomial factoring algorithm would be galactic. (FWIW, Knuth believes that P=NP and that it has no practical consequences.)
varjag · 2026-10-26 23:10:25 UTC
Imagine you're trying to prove that water is wet (P!=NP). You lack a formalism that could make sense at building a proof even though pretty much everyone agrees from empirical evidence that the water is indeed wet. A promising attempt at building one such formalism was just demonstrated by a model to be a dead end.
jaaron · 2026-10-26 23:48:17 UTC
I like this, but the actual finding is a bit different. Trying to keep the water is wet makes this awkward, but I believe it's more like:

Everyone agrees that water is wet (P!=NP), but no one can prove it. In the meantime, a whole field of computer science was built on a stronger belief (ETH): that water, at its worst, soaks. Turns out, even at its worst, water only makes things damp. It's still wet. That said, this finding did produce a new measurement of wetness.

pizzafeelsright · 2026-10-27 02:40:56 UTC
At certain temperatures water is indeed not wet.
grumbelbart2 · 2026-10-27 11:27:26 UTC
Some say water is never wet, it makes wet.
manquer · 2026-10-27 01:16:35 UTC
Not the best analogy; water is famously not wet; it makes a surface wet is the common consensus ; wetness is being a property of a surface
tavavex · 2026-10-27 02:31:26 UTC
No, it is famously a pointless internet debate with no settled answer. There is no scientific definition of what can or can't be wet, saying that wetness only applies to surfaces is just an opinion. It's an entirely linguistic question, and most people would say water is wet. If you want more than descriptivism, the common definition is something like 'containing or being covered with liquid', and I think most people would agree that a mass of water contains water.
zeroonetwothree · 2026-10-27 01:39:42 UTC
A nontrivial % believe P = NP with some reasonable probability. I wouldn’t say it’s all that settled unlike say RH
kibwen · 2026-10-27 01:50:07 UTC
Anyone credible? A nontrivial number of people also believe that humans used to ride dinosaurs around like in the Flintstones.
aleph_minus_one · 2026-10-27 02:32:06 UTC
> Anyone credible [who believes P=NP with some reasonable probability?

Do you accept

- Moshe Y. Vardi [1]

- Anil Nerode [2]

- Donald Knuth [3]

to be credible? Source for the statements that they consider P=NP to be possible: [4]

And you may include me in the list of credible P=NP believers because treat myself as a credible authority, i.e. when I ask myself whether something is right, I consider myself to be much more credible than some famous scientist. ;-)

(to be very clear: the previous paragraph is rather a clear statement against this kind of "hero worship" with respect to mathematical or scientific problems. One should consider the evidence by oneself instead of believing in P!=NP because lots of computer scientists claim all the time that this is likely true, or consider P=NP now to be possible just because some famous computer scientists consider it to be possible)

---

[1] https://en.wikipedia.org/w/index.php?title=Moshe_Vardi&oldid...

[2] https://en.wikipedia.org/w/index.php?title=Anil_Nerode&oldid...

[3] https://en.wikipedia.org/w/index.php?title=Donald_Knuth&oldi...

[4] https://en.wikipedia.org/w/index.php?title=P_versus_NP_probl...

lioeters · 2026-10-27 02:56:54 UTC
> The main argument in favor of P ≠ NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. — Moshe Y. Vardi

That sounds particularly relevant in how AI-assisted/driven mathematical research is changing the game, where previous assumptions based on human experience/effort are being overturned unexpectedly.

jibalt · 2026-10-27 03:14:20 UTC
Note that, while Knuth believes that P = NP, he doesn't believe that it will have practical applications because the exponents and/or constants will be galactic.

> to be very clear: the previous paragraph is rather a clear statement against this kind of "hero worship" with respect to mathematical or scientific problems.

No, it's an irrational rejection of the notion of expertise. The experts are not "heroes", they are simply people who have done vastly more study than folks like you or me. e.g., if Magnus Carlsen looks at a complex chess position and says that white is winning, I will trust his judgment far more than my own.

eluru · 2026-10-27 06:12:55 UTC
stack overflow worthy levels of ego
vbezhenar · 2026-10-27 02:17:43 UTC
Water is not wet. Human lacks water sensor. All the sensors we have a temperature ones so we sense "wet" as a combination of temperature and visual information. Close your eyes, touch water of your skin temperature and you won't sense it. It's not wet.
foo12bar · 2026-10-27 02:22:09 UTC
Stick your head in it and breathe. You'll know.
pizzafeelsright · 2026-10-27 02:41:22 UTC
Fog, clouds, steam, ice.
aleph_minus_one · 2026-10-27 02:45:09 UTC
There exist lots of non-wetting liquids in which humans cannot breathe.
foo12bar · 2026-10-27 12:01:04 UTC
Your lungs have sensors that can detect being coated by a liquid which invokes coughing. In that sense, you can detect wetness.
teiferer · 2026-10-27 12:39:45 UTC
They detect being coated, no matter liquid or not. (Source: Parents who smoke. And don't tell me the crap they are inhaling is a liquid.)
jibalt · 2026-10-27 03:17:17 UTC
Not only is that statement not true, as noted by others, it's also not at all relevant to what you're responding to.
foo12bar · 2026-10-27 10:37:55 UTC
Oh, so if you stick your head in a liquid and breathe you wouldn't know?
teiferer · 2026-10-27 12:37:45 UTC
Sticking your head into non-liquid substances can have the same outcome. It therefore is not a suitable method for detecting wetness.
pmontra · 2026-10-27 05:27:16 UTC
Sand too, even when dry. But OK, metaphors have limits.
stavros · 2026-10-27 07:50:01 UTC
By that definition, a vacuum is wet.
foo12bar · 2026-10-27 12:02:19 UTC
Trying to beathing in a vacuum would not feel the same as breathing in a liquid.
stavros · 2026-10-27 12:04:09 UTC
What would feel different?
carefree-bob · 2026-10-27 03:59:25 UTC
I'm beginning to wonder whether P!=NP is undecidable.
teiferer · 2026-10-27 12:34:54 UTC
That statement is nonsensical for the usual formal notion of "undecidable" which is about infinite sets of inputs that a machine is asked to classify as "yes" or "no" instances, also called a decision problem.

P-vs-NP is no such decision problem. It has a single instance, we just don't know its validity.

IAmBroom · 2026-10-27 13:26:10 UTC
It was not a formal statement.
jltsiren · 2026-10-27 00:00:50 UTC
It's been a long time since I seriously thought about complexity theory, but I'd say no. For similar reasons to why complexity class E is not closed under polynomial-time reductions.

The most important component in the time bound is of the form 2^{n / polylog(n)}, which is subexponential. But if you have reduction from another problem that increases instance size quadratically, the algorithm for the other problem is no longer subexponential. Which means we are still essentially in the same neighborhood as before.

It's a huge result if true, and probably the first major AI result that affects the papers I read. But since the boundary in the hypothesis was kind of arbitrary, breaching it should not significantly change our intuition on complexity classes.

cwillu · 2026-10-27 01:01:28 UTC
How much effort has been expended on optimizing those reductions though? I have a harder time believing that one can hang one's belief in P!=NP on that particular hook.
jltsiren · 2026-10-27 02:05:32 UTC
The challenge is the initial reduction from an arbitrary problem in NP to the problem you want to prove NP-complete.

In the usual approach, you assume a nondeterministic Turing machine (or equivalent) that solves the problem and a time bound (which can be an arbitrarily large polynomial). You then create a boolean expression that can be satisfied if and only if the Turing machine accepts the original problem instance. Unfortunately all constructions so far have included the time bound as a factor of the size of the expression.

rao-v · 2026-10-27 03:20:33 UTC
There are so many just barely sub-exponential function shapes between 2^(n / sqrt ln n) {this result} and 2^(log n) {polynomial time}!
hakuseki · 2026-10-27 02:39:47 UTC
I think the bigger issue (for someone hoping for P=NP) is that there's a huge gap between "polynomial" and "exponential." Even if it were the case that all NP problem classes had subexponential decision algorithms, that would not get us close to P=NP.
CaptainNegative · 2026-10-27 00:38:00 UTC
I think it would have to if you're honest with yourself. Any proof of a novel implication of P=NP, such as !ETH, should increase your belief in the two sets' equality. Just as any novel implication of P≠NP should adjust your belief the other way.

My thesis was around showing implications of few different hardness conjectures. So grounded was ETH that I introduced it in a side note as Conjecture 0 after Conjectures 1 and 2. I don't think it's easy to express how substantial of a Bayesian update this is all around.

ComplexSystems · 2026-10-27 00:55:29 UTC
I think that it'd be funny if the polynomial time SAT solver was just "send your SAT instance to Astra and have it try to solve it for a few hours."
GuB-42 · 2026-10-27 01:38:18 UTC
I wonder if there are proofs regarding what neural networks like the transformer can solve. Because fundamentally, Astra is just a bunch of matrix multiplications and a few well defined non-linear functions.

Anyways, most of the times, SAT can be solved quickly, but not always, so getting the answer from Astra in polynomial time doesn't prove much unless you can also prove that it always does, no matter the input.

ViscountPenguin · 2026-10-27 02:02:33 UTC
Iirc, there's a big difference between the computational complexity of what a transformer can solve and what it can solve in practice; what it can solve in practice tends to come from things like singular learning theory (which describes the forms of generalizations that a given ML algorithm can make), but I think (iirc) that transformers can compute a pretty broad class of O(N^2) functions?
anon291 · 2026-10-27 02:45:07 UTC
For the umpteenth time a transformer is an arbitrary turning machine due to the fact that it has a theoretically limitless tape (the context).

A single transformer step is simply O(1) (for a particular parameter size), but it applied a potentially infinite number of times.

Thus while a single transformer cannot solve any problem, a transformer system applied in the normal way can solve any computable problem.

geraneum · 2026-10-27 06:22:00 UTC
The context acting as a "theoretically limitless tape" while simultaneously the step being O(1) are contradictory. You cannot have it both.
anon291 · 2026-10-27 06:26:38 UTC
It's not contradictory at all. The dfa at each step of the turing machine model is also o(1).
geraneum · 2026-10-27 07:05:30 UTC
Of course it is. You’re conflating a turing machine with a transformer. Transformers don’t have a local read/write head. The [self] attention is over the whole context, which makes each step O(N) at best (with caching) and O(N^2) w/o.
anon291 · 2026-10-27 15:21:02 UTC
of course it has a read write head. In fact it has N read / write heads equal to the size of the context since each latent state is updated with the results of the cross attention mechanism at each step.

Alternatively, you can view the '<unknown>' token that is dynamically driven to the embedding of the output token to be the write head. Either way, the simple truth is that you can train a transformer system (i.e., an iteratively applied transformer) to simulate an arbitrary turing machine.

vidarh · 2026-10-27 07:10:33 UTC
The context can change each time. To implement a UTM only requires 2 states and 3 symbols or the reverse.

So if you use the context not as a tape in itself, but as an io channel to read/write an infinite tape, the context for any given step can remain fixed in size, and so the step itself can be O(1).

geraneum · 2026-10-27 09:08:47 UTC
Any basic lookup table is turing complete if you bolt an external infinite tape and read/write head onto it. But then that’s moving the goal post since the context wouldn’t be the “limitless tape” and it’s not a transformer “in the normal way” because turing completeness would be coming from external io and not from auto regressive self attention. Different topic.
GuB-42 · 2026-10-27 14:17:08 UTC
It depends on what you say is O(1). A theoretical Turing machine has an infinite tape that can be accessed in O(1), but in real life, it would require a machine of an infinite size.

Same idea for that transformer, it needs an infinite context, and it is an infinitely big machine, but with that level of abstraction, it processes a token in O(1).

In practice, there is no such thing as O(1) on arbitrarily sized data, there is no such thing as infinity either, it is just an abstraction.

geraneum · 2026-10-27 15:01:38 UTC
> Same idea for that transformer

It’s not the same for transformers, especially not with the theoretical infinite context. It simply doesn’t process tokens in O(1) in your given setup.

In practice, with frontier LLMs, it’s of course more complicated, and also they don’t reveal how they do lookups, but still the theoretical limit applies regardless.

Do you mind elaborating or perhaps providing some reference as to why you think transformers should be similar to a Turing machine on this specific criteria?

jibalt · 2026-10-27 03:05:14 UTC
No. Scott Aaronson said that it changed it from 3% to 5% for him, which is a lot more generous than I would be (but he knows far more about the subject than I do).
randallsquared · 2026-10-27 03:10:29 UTC
So, what I heard was "No, and here is a good reason it should be 'yes, some'."
jibalt · 2026-10-27 03:33:48 UTC
The question was

> does this update your priors significantly in the direction of P=NP?

My answer is no ... and Aaronson's answer would also be no ... clearly he doesn't view a change from 3% to 5% to be significant ... his response downplayed the significance of !ETH in re NP?=P. So apparently you downvoted me for simply stating my own opinion while you completely misunderstood what it was an opinion of.

baobabKoodaa · 2026-10-27 06:08:28 UTC
A change from 3% to 5% is significant. It's almost doubling the probability.
maybeOneDay · 2026-10-27 11:05:44 UTC
Buying two lottery tickets doubles your probability of winning. Does it significantly move your priors?
zarzavat · 2026-10-27 04:09:43 UTC
It might make the third option, that P vs NP cannot be proven true or false, somewhat less likely.
teiferer · 2026-10-27 12:40:42 UTC
Could you elaborate?
calf · 2026-10-26 21:54:02 UTC
In the Star Trek Voyager capstone episodes titled "Scorpion" parts 1 & 2, Chakotay explains to Janeway the behavior of the Borg through the parable of the fox and the scorpion making a transactional deal to cross the river together. After reaching the shore, the scorpion stings the fox, and the dying fox asks why. The scorpion replies, "Because it is in my nature."

(Upside of the story is Captain Janeway's trusted crew works together to formulate a trick up their sleeve precisely in case of predicted contingency...)

paxy · 2026-10-26 22:03:47 UTC
Title is no doubt crafted to get ahead of the usual online backlash, but here’s the actual announcement:

> We are announcing three new discoveries in mathematics, computer science, and physics about harmonic analysis, complexity theory, and quantum field theory.

1. Local smoothing and the Kakeya conjecture

2. The Exponential Time Hypothesis is false

3. Existence of quantum chromodynamics and completions of the Standard Model