253 points jonluca 2 hours ago 112 comments
rbranson 2 hours ago | parent
> The Exponential Time Hypothesis is false
krackers 2 hours ago | parent
>We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula [in superpolynomial but subexponential time]
JonChesterfield 2 hours ago | parent
JonChesterfield 2 hours ago | parent
mattr03 1 hour ago | parent
looks like the real proof is in this file
JonChesterfield 1 hour ago | parent
sebzim4500 1 hour ago | parent
Proof is at https://github.com/openai/math/tree/main/lean/OAI/Algorithms...
ollin 1 hour ago | parent
Sniffnoy 2 hours ago | parent
levocardia 1 hour ago | parent
>Our models produced a natural language proof for Yang–Mills existence on September 9th, 2026
And presumably they are just missing the "mass gap" part of it.
Very clearly these were the results of taking big swings at all millenium prize problems.
mlinsey 2 hours ago | parent
novaRom 1 hour ago | parent
rcpt 1 hour ago | parent
Would be funny if the most famous problem turns out be an example though
skew-aberration 1 hour ago | parent
rcpt 30 minutes ago | parent
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.
noslenwerdna 19 minutes ago | parent
_dain_ 27 minutes ago | parent
varjag 1 hour ago | parent
jaaron 25 minutes ago | parent
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.
jltsiren 13 minutes ago | parent
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.
calf 2 hours ago | parent
(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...)
mudita 1 hour ago | parent
paxy 2 hours ago | parent
> 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
Rudybega 1 hour ago | parent
Kakeya / local smoothing (math): The result would resolve the Kakeya conjecture and Stein’s restriction conjecture across all dimensions together. Mathematicians had been making progress one dimension at a time, so this would settle a whole family of central harmonic analysis problems at once.
ETH is false (computer science): ETH has been used as a computational hardness premise in hundreds of papers, so a disproof would undercut a large body of existing complexity results. It would also change what researchers think is achievable for efficient computation.
QCD existence (physics): It would give a rigorous mathematical foundation to the theory of the strong force, which physicists have used for decades without proving it’s well-defined. It also bears on a Millennium Prize Problem.
emil-lp 1 hour ago | parent
On the positive side, suddenly there's a whole bunch of open problems!
dekhn 1 hour ago | parent
Turning the question arouhnd: what would be the most impactful thing for OpenAI or Anthropic to do to show large breakthroughs?
demibabs 55 minutes ago | parent
Kotlopou 51 minutes ago | parent
ETH sounds more like there's a path it could become important? In general, the recent complexity results suggest that a) our intuitions about that world are unreliable, and b) the truth seems to be insanely complicated. I mean, new faster multiplication algorithms in 2026, what the hell? How can we say anything about the full space of all possible algorithms?
redox99 33 minutes ago | parent
Or is such understanding reliant in experimentation because there are "hidden constants" we can't figure out with math alone?
abetusk 28 minutes ago | parent
[0]:
> We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula. For every fixed k ⩾ 2, on a formula with n variables and m clauses, our algorithm uses $poly_k (n, m)$ space and runs in time $(n + m)^{O_k(1)} 2^{n/(\log n)^{1/2 + o(1)}}$
The dominant term there is (roughly) $2^{n / (\log n)^{0.5}}$, so still superpolynomial but less than exponential. Fucking wild.
[0] https://github.com/openai/math/blob/main/preprints/The-Expon...
esalman 2 hours ago | parent
I looked over the announcement for any substantial contribution, and found they're donating $5 million to a research foundation.
$5 million might sustain 5-10 PhD students for 5 years.
Maybe it's just me but I think they should contribute more in exchange for forcing the scientific community into paying for tokens to generate slop and then pouring their time into verifying or falsifying the slop.
quantumspandex 1 hour ago | parent
LPisGood 1 hour ago | parent
esalman 28 minutes ago | parent
dooglius 1 hour ago | parent
geysersam 1 hour ago | parent
LPisGood 1 hour ago | parent
krackers 1 hour ago | parent
Showing 3SAT (technically #3SAT) can be solved in less than EXPTIME resolves this. It's only slightly subexponential, not even quasipolynomial, but it is a very surprising result. And that too a constructive algorithm.
Edit: Apparently not true, the constructive algorithm given may not survive under reductions. See discussion in https://news.ycombinator.com/item?id=50251661
3abiton 1 hour ago | parent
mentalgear 1 hour ago | parent
artninja1988 1 hour ago | parent
titzer 1 hour ago | parent
The reality that Science is a grind and there are thousands of new results every year discovered by regular humans who use a regular human process to cross-check and review.
Treating every result from the AI like a gift from god is getting tiring.
quantumspandex 1 hour ago | parent
sgillen 1 hour ago | parent
These are really big results from AI, if a human had come up with them we would also be making a really big deal out of them too (maybe not as big of a deal, part of the excitement is that this was from AI and more results of this magnitude may soon follow).
metalsiliconYT 1 hour ago | parent
sebzim4500 1 hour ago | parent
T-A 1 hour ago | parent
karmasimida 1 hour ago | parent
1ahsgt 1 hour ago | parent
Proud to funnel money through the Simons Foundation, which is an AI booster itself and completely aligned with OpenAI.
They make it very hard to enjoy a single result with the business and the politics being so dirty.
jwpapi 1 hour ago | parent
I’m currently reading Africa by John Reader which covers a lot of humanity storyline. From HN I get the humanity achievements that are happening right now.
The feeling digesting both daily is in order of magnitudes bigger than what any really exciting tv show did to me.
I honestly at this point don’t know anything about what could be possible and what couldnt.
I understand that this is really freightening, but also especially ETH being false gives even more hope that some fundamental problems could be solved in our lifetime, for example understanding universe, aging, colonization of planets and also our limits. I know I’m the minority, but these answers really interest me.
kypro 1 hour ago | parent
There are infinitely many more ways to kill and torture a human than to save one.
adverbly 51 minutes ago | parent
dekhn 1 hour ago | parent
Even with aging, our efforts are better spent increasing quality of life across humanity than helping a few rich people live to 150.
jwpapi 54 minutes ago | parent
Re life quality: Sure technical advancement can lead to cheaper electricity, better materials discovered, disease prevention and a lot of other stuff. A lot is hold back by complexity.
I don’t want to make a call that this will happen and that it’s a net-positive for society. I’m just saying the technical advancements is interesting and enablin.
hei-lima 1 hour ago | parent
mindwok 1 hour ago | parent
__MatrixMan__ 1 hour ago | parent
It feels a bit like having "visited" a place because you had a layover there.
brap 50 minutes ago | parent
We should remember that math exists primarily to serve a purpose and that purpose is not being a fun puzzle hobby for a select few mathematicians.
Imagine a programmer telling their boss it’s not about working software it’s about the journey of writing the code. Good luck getting hired.
I think if pro mathematicians don’t change their tune quickly they will soon see their funding approach zero.
Kotlopou 47 minutes ago | parent
unknownian 34 minutes ago | parent
brap 12 minutes ago | parent
cman1444 50 minutes ago | parent
ChemSpider 57 minutes ago | parent
(Never would mean AI will be used in future labs like a fancy calculator, but not much more changes)
dannykwells 42 minutes ago | parent
Routine8502 37 minutes ago | parent
Also, fwiw I have a personal test problem I give to every frontier model on release, which is to ask it to final a realatively obvious solution (in hindsight) to a minorly important open problem in my field. I know the answer, but havent gotten around to writing it up yet (it's really not that important). Every frontier model (so far) just regurgitates existing solutions.
szvsw 27 minutes ago | parent
Edit: to be clear, I completely believe your experience - just pointing out that it might be interesting for you to actually “try” to solve it thoroughly with the tools, though it is obviously hard to do that in a fair way when you know the solution.
marshray 26 minutes ago | parent
aborsy 1 hour ago | parent
rcr-anti 1 hour ago | parent
Daniel_Van_Zant 1 hour ago | parent
My guess is that in formally verifiable domains you can use RL-esque processes to get lots of good high-quality training data with reward signals (does it verify?), but the same does not apply to "scruffier" work. I would also imagine that the data volume of high-quality scientific work in "scruffy" domains is too low for the large language models to have a good manifold for "high-quality biology research". Would love to be proven wrong if anyone knows of anyone doing great scientific work with large language models in non-verifiable domains though.
rcpt 1 hour ago | parent
AI has dominion over the digital world, when it can verify things in Lean it's able to crush problems like they're a game of Go.
But when the real world and digital world don't quite connect AI is bottlenecked.
crabmusket 50 minutes ago | parent
itchyjunk 1 hour ago | parent
Creamsicle47 1 hour ago | parent
serioussecurity 59 minutes ago | parent
Many of the harnesses used to search for solutions rely on quick/cheap correctness checks to discard incorrect hypotheses. With something like biology, you might need to run a wet lab experiment to reject an idea. This can add days per iteration, slowing progress down by a factor of 100 or more.
The sad reality is that many computational approximations for biological phenomenon are relatively weak and lack the predictive power we need.
Frost1x 48 minutes ago | parent
With that said part of the reason some domains may not have robust cheap verifiers is because they’re difficult to produce already, so it may be a bigger lift.
szvsw 33 minutes ago | parent
In an area I am more familiar with though still not my domain: when the stiffness matrix and computational linear algebra methods collide, it unlocks a world of computational structural design and analysis by commoditizing the underlying mathematics. This is a simple example, but you get the idea.
Obviously with CFD, mechanics, etc there is always massive work being done to try to unlock new computational methods, faster/parallelizable computational methods, differentiable ones, etc etc, but the general feeling is that the core physics are well modeled (NS millennium problem not withstanding) and are not lacking in predictive power for useful applications. I would have assumed that the same would be generally true for computational biology etc, so just curious to hear you elaborate more. It seems plausible to me that turning the brute force of “the models” (as in, swarms of AI compute) to work on/develop/solve/address whatever representational problems there are in the computational approximations/numerical methods you mention, particularly if that is a bottleneck to performing more extensive methodological/experimental exploration in silico to enable better exploitation/use of limited resources in wet lab.
Again, I know nothing about computational biology, just stating my intuition and curious what your take is. Probably the limits of my knowledge can be demonstrated by the fact that the only modeling methods that come to mind as being vaguely relevant would be, like,… molecular dynamics, maybe discrete element method in a weird way but doubtful, and various pop science understandings of protein folding etc.
kypro 45 minutes ago | parent
Obviously it's easy to understand why having strong abilities in maths and coding can help with solving problems in physics. But it's also true of knowledge and mental models more broadly.
For example, say somehow you managed to train a frontier model without any data about elephants. If you did this it would be relatively easy to later train elephants into the weights. You'd basically just need to train it about elephants at a very superficial level. After all, it it already knows what a mammal is. It knows what legs are. It knows what eyes are. It understands how it's digestive system works. All the things that makes the biology of elephants difficult doesn't need to be learnt from scratch.
I assure you people on HN will be surprised at how quickly frontier models will become competent in domains that are harder to RL. They won't need anywhere near as much data as people currently believe.
Kotlopou 40 minutes ago | parent
Kotlopou 1 hour ago | parent
They are staying on top of the exact formulations that spread like memes. I think this one was unfortunate. It's an analogy for a new type of thing that stops attempts to figure out what thing that is.
That said, uh, let's go? Let's see if OpenAI earns some goodwill here. It probably can't go worse than the last math drop!
vatsachak 9 minutes ago | parent
adverbly 1 hour ago | parent
Much better!
> For the computer science collaboration, the group has decided to make the natural language proof and Lean formalization public immediately, and we are publishing them directly to our GitHub repository. For the physics collaboration, the group has decided to hold off on releasing the AI-produced artifacts and instead work on writing it up themselves.
> All of these approaches involve tradeoffs. On the one hand, the collaborations empower experts to foster unpacking the results and contextualizing them in the broader academic community. On the other hand, choosing initial shepherds necessarily shapes who gets involved first and creates asymmetry of information. We welcome feedback on how to broaden participation and make this process more useful.
Very good!
I was highly critical of their approach with the earlier mathematical publications, but this is much improved.
Most importantly, they aren't releasing slop papers that would never have been published in any self-respecting journal or made it past a deep round of peer review questioning.
> We are committed to ensuring funding for researchers to independently examine, explain, and build on the results above.
> We continue to invite feedback on the best way to disclose results and engage with scientists to accelerate discovery.
Well done!
Now you need to actually LISTEN to the community and the feedback, so you aren't done yet, but this is a much better start than last time. Keep it up!
lukeplato 1 hour ago | parent
absolutely insane
doctoboggan 1 hour ago | parent
[0]: PBS space time watcher
Kotlopou 58 minutes ago | parent
T-A 28 minutes ago | parent
This part,
The existence proof pertains to the simplest grand unified theory that includes the gauge fields and fermions of the Standard Model
looks like a reference to SU(5) GUT from 1974:
martinhath 1 hour ago | parent
Also glad to see that one of the authors of the paper stating it is also in the loop here.
2026 is weird.
Kotlopou 1 hour ago | parent
(Elliot Glazer seems in general to be a pretty good source to follow, however he does that...)
Kotlopou 42 minutes ago | parent
> I occasionally talk to experts on all the MP's. Their rough summaries on what is needed to solve them usually go:
> Hodge: not a clue
> BSD: not a clue
> RH: not a clue
> P vs NP: not a clue
> Yang-Mills: "Well..."
Insimwytim 53 minutes ago | parent
Let's throw in more of that stuff, so they wouldn't look at the financials.
stabbles 48 minutes ago | parent
Mathematics and computer science are turning into an empirical science
dannykwells 41 minutes ago | parent
nixonaddiction 35 minutes ago | parent
measurablefunc 28 minutes ago | parent
zone411 11 minutes ago | parent
Kakeya conjecture — #38
Fourier restriction conjecture — #46
Local smoothing for wave equations — #187
Bochner–Riesz conjecture — #190
Exponential Time Hypothesis — #43
Strong Exponential Time Hypothesis — #63
vatsachak 8 minutes ago | parent
As a non abelian harmonic analysis PhD I am very happy