[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...
Turn this loose on LHC data ASAP.
(Never would mean AI will be used in future labs like a fancy calculator, but not much more changes)
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.
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.
I think the solution is easy enough that any competent colleague would come up with it. Some variant on it has probably even been published (hence why I'm not chomping at the bit to publish). I think it comes down to the models being extremely spiky, and the problems they're trying to solve being easily verifiable in code.
Also, goes without saying, but put Sam Altman in jail, obviously.
It feels a bit like having "visited" a place because you had a layover there.
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.
Thinking in such a utilitarian way feels like a flavor of Meditations on Moloch.[1] Just look at how short-term, quarter-to-quarter thinking is affecting the economy and the lived experience of every human on earth. It’s horrible.
[1] https://slatestarcodex.com/2014/07/30/meditations-on-moloch/
Your formulation is a little bit exaggerated, but I (and many, though far from all, programmers) would agree with the following more "tame" formulation:
Getting software to solve a business problem in an elegant and maintainable way means that we got the abstractions right. Similarly, if a software can easily and elegantly be modified to cope with new business problems, it is also a strong sign that we got the abstractions right. In this sense, the business problems that the software solves are indeed just waypoints on the journey of finding the proper elegant abstractions for putting the business problems into code.
Turning these novel insights about "good" abstractions into code and programming languages enables the team to iterate faster and generate business value faster. So, appreciating that it indeed all about the journey means a commitment towards an approach to accelerate the rate with which the team can turn business insights into code and code into business value.
I know that many managers do hate such a formulation, but I stand behind it.
Many of the OpenAI results can be made human-understandable, so it's better than the four-color theorem example.
Let's say it's possible to know an alien civilization exists 100 million light years away from their waste heat. But that's all we know and it's unlikely we'll ever interact with them.
Was the question of whether we're alone still "valuable"? Wouldn't a lot of philosophy and even some physics fail to meet your definition of valuable?
But to give a brief answer to your question directly: In my view, and I think many if they really thought about it, the point of life is to overcome. If there is an AI that spits out the answer to questions that don’t directly impact human wellbeing instead of letting humans explore the answer at our own pace, we should question whether that AI is worth keeping around or at least relying on too much.
Obviously the question is more nuanced when it comes to math, because even pure math can have applications to understanding reality and improving human wellbeing.
So the question then becomes what do we do with the AI when it can both improve our wellbeing and remove meaning from our lives? Is a life without struggle worth a life without meaning? Personally I don’t think so, so I think we have to optimize all of the benefits of AI while essentially taking a harsh stance against all the harms. Currently the main harm is to education, and that’s why I think we should question and probably even disallow its use by students still working to demonstrate their skills.
Also glad to see that one of the authors of the paper stating it is also in the loop here.
2026 is weird.
absolutely insane
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.
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.
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.
Would be funny if the most famous problem turns out be an example though
EDIT: I'm 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.
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.
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.
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.
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.
1. Biology has a very nasty habit of not cleanly abstracting. It's not like we can treat every protein as a "diffuse mass" without losing a ton of important interactions. This is unlike something like CFD where you can treat a mass of water molecules with certain constants. Think of something like cancer: a small mutation to a DNA strand can cascade into a tumor. You have to deal with the mutation happening at an atomic level while scaling to a whole organism (yes I know there's models that can approximate this, but they can't capture all the interactions).
2. This brings us to modelling at the atomic level. To model a system of atoms with the Schrödinger equation, it naively scales O(6^n) per particle. Note that means every nucleus and electron, so if you have say 10 carbon atoms and 22 hydrogen you're already at 10^127 operations. We can cut corners a bit and end up with something like CCSD which scales O(n^7), or cut more corners and scale O(n^3) for DFT. DFT is pretty much the last method where bond forming and breaking is modelled, so after more corner cutting you lose losing reactions, which are important for understanding why something is happening. Most protein folding simulations (moreso prior to alphafold) run a very crude approximation that models atoms as balls on springs (things like AMBER and CHARMM), which obviously can't handle reactions.
3. If this wasn't bad enough, you also can only move through time at about 1 femtosecond (10^-15), so it takes a ton of simulation steps to get even a nanosecond in. Forget millisecond or second lengths where things start to happen.
So, while the math of the physics exists, computationally it's practically intractible. There's some exciting work with something called Machine Learning Interatomic Potentials (MLIP) which approximate DFT using a neural network which are about 1000x faster than DFT, and iirc scale much more linearly (look at things like MACE and orbmol if you're curious). So we're making progress, but we've gone from so ridiculously impossible to pretty much impossible for large systems.
I have a couple ideas about developing custom microchips to make this faster, which is why I'm pursuing this, but there's still a massive way to go!
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.
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.
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.
>We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula [in superpolynomial but subexponential time]
> The Exponential Time Hypothesis is false
Proof is at https://github.com/openai/math/tree/main/lean/OAI/Algorithms...
looks like the real proof is in this file
>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.
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
(Elliot Glazer seems in general to be a pretty good source to follow, however he does that...)
> 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..."
As a non abelian harmonic analysis PhD I am very happy
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=50252769
Mathematics and computer science are turning into an empirical science
[0]: PBS space time watcher
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:
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!
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.
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).
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.
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.
Even with aging, our efforts are better spent increasing quality of life across humanity than helping a few rich people live to 150.
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.
There are infinitely many more ways to kill and torture a human than to save one.
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!
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.
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.
On the positive side, suddenly there's a whole bunch of open problems!
Turning the question arouhnd: what would be the most impactful thing for OpenAI or Anthropic to do to show large breakthroughs?
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?
Or is such understanding reliant in experimentation because there are "hidden constants" we can't figure out with math alone?
> 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
(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...)
Let's throw in more of that stuff, so they wouldn't look at the financials.
Yay, shills are here with downvotes!