> The Exponential Time Hypothesis is false

looks like the real proof is in this file

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

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.

>We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula [in superpolynomial but subexponential time]

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

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

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

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

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.

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.

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.

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.

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...

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.

> 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.

I kist thought it was interesting that there are receptors that can detect wetness, just not on the skin. It was a joke pointing that out.

Fuck.

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

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.

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.

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.

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.

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.

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.

> In fact it has N read / write heads equal to the size of the context

And what is the asymptotic notation when computation scales linearly with the size of context?

> Either way, the simple truth is that you can train a transformer system

Which still doesn’t mean they have a read/write head or have O(1) complexity for token computation with “infinite context”.

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).

The consequence of that is that the original question GuB-42 raised is pretty pointless too. An "inert" transformer effectively has limitations, but as typically used it trivially becomes Turing complete, and so the class of problems it can solve is the exact same class of problems almost any of our other computational devices can solve.

And if you want to point out that this externalises all of what actually matters if we are talking about e.g. intelligence, then yes, it does. But by extension you can trade complexity of the tape for complexity of the machine, and so you can internalise any part of the problem that can be solved with a finite section of tape as a single state transition (trivial proof: For a given machine M with finite state, you can make your machine N execute those steps as a single state transition by having N run M on a state transition.)

To extend that to where I assume they'd want to go in the first place: A transformer wrapped in a loop with access to "just" a "tape head" can "only" be limited from being theoretically able to get all the way to human level intelligence if human brains depend on computations that exceed the Turing computable. But that is no different from any other Turing complete device.

Of course that says nothing of whether it's a practical way of getting there.

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.

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?

> 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.

(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...)

https://en.wikipedia.org/wiki/The_Scorpion_and_the_Frog

> 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

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.

>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.

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

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?

Why haven't these theories had more impact on materials science? We use DFT and other greatly simplified approaches (with tremendous results) but still I suspect we are massively underperforming in terms of producing materials with useful properties.

The new faster multiplication algorithms are both galactic, are they not?

It does not seem surprising to me at all that AI can find new galactic algorithms that are not of any direct use (at best they can guide us to find better solutions that are non-galactic).

What would be surprising and interesting is if AI can find a new floating point multiply-add that is 2X faster per operation than the current fastest chip implementations. That would immediately have billion+ dollar implications. The teams who already work on this have excellent approaches and invest enormous amounts into tiny improvements already; there are probably not much low-hanging fruit there (proponents of using AI for chip design improvements have impressive claims, but unclear that any of those really worked out in reality).