r/singularity • u/likeastar20 • 1d ago

AI Internal Claude research model also independently refuted the Exponential Time Hypothesis on October 16, with 14M output tokens and no human input.

Post image

https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth

917 Upvotes

96% Upvoted

174 comments sorted by

102

u/jkpatches 1d ago

So what are the real world consequences of this. Are there real things that depend on the hypothesis being correct?

180

u/bachmensch 1d ago

To quote u/kaereljabo:
AI agents tried to solve P vs NP using the Exponential Time Hypothesis being true as a possible route, because if they could prove ETH being true, then P!=NP
The AI agent failed, it instead proved ETH is false (quite shocking because many people believed ETH is true). So this agent failure to prove P vs NP via ETH as true is a success in a sense.

98

u/Brilliant-Weekend-68 1d ago

So what are the real world consequences?

98

u/exophades 1d ago

None for the ETH being false. But, if, God forbids, P turns out to be equal to NP (with a constructive proof), the consequences would be cataclysmic.

7

u/kr0n0sShrugg3d 23h ago

Cataclysm followed by utopia

5

u/aturtledude 22h ago

Couldn't the result eventually lead to improvements in SAT solvers? That would have a huge impact.

6

u/LookIPickedAUsername 18h ago

Nah, P=NP would almost certainly be meaningless in practice.

A polynomial time algorithm doesn’t have to be practical. O(nGraham’s_Number) is still technically polynomial time.

2

u/The_Scout1255 23h ago

Im hoping P = NP or problems are even easier then P = NP

13

u/Objective-Rip3008 17h ago

Most of the weirdo math problems have no real world consequences. The thinking behind them is just that the journey to solve the problem will result in learning new math that is useful rather than the question itself being useful

3

u/qeadwrsf 10h ago

A math guy once told me math is useful because it narrows down what physics people should work on.

2

u/RedditTipiak 23h ago

The machines just dropped a Rick and Morty joke on the world, akin to "everything you believe in is wrong, everything you've been working on is meaningless".

1

u/Lighthouse_seek 18h ago

Nothing yet. The dream that P=NP lives on for now

1

u/Grounds4TheSubstain 19h ago

Is that substantiated somewhere or just speculation? It certainly seems plausible, I just haven't seen any of the labs confirm that.

18

u/RemusShepherd 19h ago

The Exponential Time Hypothesis (ETH) is a stronger constraint than P=NP, but it's in the same ballpark. It tells us how fast it's possible for an algorithm to be optimized. While P=/=NP constrains algorithms to being slower than polynomial time, ETH constrains them to being slower than exponential time which is even slower than polynomial.

There won't be many real-world consequences for ETH being disproven. There might be a few minor optimizations to encryption (or encryption breakers) and other complicated mathematic algorithms.

The exciting/terrifying part is that it's a stepping-stone to proving P=NP. If that happens all hell breaks loose as all encryptions fail.

2

u/dapzar 8h ago

P=NP would not mean that all encryption fails. That would require a factorization algorithm with practical exponent and practical constants. That would not necessarily be implied by P=NP. That’s a big oversimplification that gets told CS communication to lay people.

Disproving the ETH is also not necessarily a stepping stone towards P=NP. That would only be possible to see in hindsight (if there is an entire path, we might see it as an early step). If the nature of reality turns out to have P!=NP, then there are no stepping stones towards P=NP because there cannot be any paths to it period.

1

u/RemusShepherd 6h ago

If P=NP then it is possible to break encryption in short amounts of time. If it's possible, an AI that was able to prove P=NP is going to be able to make the factorization algorithm.

Disproving ETH is a stepping stone toward P=NP, because it ETH were true, P could not = NP. Maybe 'signpost' is a better term, but it is in the right (wrong?) direction.

1

u/BlipOnNobodysRadar 5h ago

 If the nature of reality turns out to have P!=NP, then there are no stepping stones towards P=NP because there cannot be any paths to it period.

just to be annoying, that assertion relies on a presumption of rationality and causality. However, existence exists therefore logically logic invalidates the logic of evaluating the constraints of reality solely within logic. So there can be paths to it, the universe could be a turtle and one of its skin flakes is a stepping stone towards P = NP or something idk I got bored halfway through this goodnight

3

u/DaShaView 14h ago

It is not a stepping stone to P = NP.

ETH true -> P =/= NP

That is one directional implication. If the left hand side is false it does not logically say anything about the right hand side.

3

u/mr_birkenblatt 12h ago

That's why they said stepping stone towards

1

u/LettuceSea 7h ago

There will be MANY real world consequences, what are you talking about? Do you know how much research, which real world shit is based, exists where the assumption was that ETH is true?

1

u/RemusShepherd 6h ago

I do not! Please, tell me a few. I'm genuinely interested.

2

u/Ok_Warthog6007 17h ago

zero consequences for this particular proof. it's really just "this particular method of proving p != np would not work"

2

u/flat5 16h ago

It's more that the search is back on for more efficient algorithms to solve some types of problems. We've shown that the fundamental barrier believed to exist actually doesn't.

11

u/piponwa 1d ago

Nearly all work on P vs NP assumed it to be true. Now it's been proven false.

21

u/tip2663 1d ago edited 16h ago

ETH doesn't prove either outcome of the P NP situation

Edit/Reply to comments: Yes

35

u/Zarathustrategy 1d ago

If it had been true it would mean that P≠NP

13

u/TieBackground453 21h ago

I think you mean that this negation of ETH doesn’t prove the P vs NP situation.

3

u/PineappleHairy4325 23h ago

Reread that sentence.

4

u/BlacksmithCapital757 22h ago

I haven’t read the paper but almost surely nothing.

There’s some algorithm for a problem that is subexponential but probably requires such large parameter sizes or is so impractical to implement that it’s a net loss until the inputs get so unimaginably huge no one could ever compute with them anyway.

But it’s a big theoretical result.

Some people may start to believe P = NP. Even if that were true, it’s been well known to be in the same situation: the polynomial time algorithm would likely be completely impractical.

0

u/No-Tap-4307 16h ago

I haven’t read the paper but almost surely nothing.

what an absurd thing to say lmao, the real world consequences for this are obviously not going to be 'almost surely nothing', in any sense.

2

u/flat5 16h ago

Ok, then it should be easy to name one.

0

u/No-Tap-4307 15h ago

I mean , I don’t need to. Read this whole thread or the internet in general about it lmao, what a redundant thing to say

Obviously you know better than everyone

1

u/BlacksmithCapital757 11h ago

The fact that you think it’s an absurd thing to say shows clearly that you know nothing at all about this stuff.

If by “real world consequences” you mean “something outside of pure mathematics and theoretical computer science,” they absolutely are going to be almost surely nothing. And, to be clear, it is a huge deal for pure math and theoretical computer science.

But a subexponental algorithm for 3SAT that doesn’t beat classical algorithms until inputs reach some ungodly number of bits that no computer could even dream of reaching changes nothing in the real world. Especially if it’s less parallelizable than existing algorithms… and reducing other problems to SAT does require multiplying the size of the problem, so any gains from subexponential are surely going to be negligible compared to that overhead…. And it’s probably like “worst case subexponential” when stuff running SAT doesn’t need to consider worst case… etc.

Improved time complexity does not at all mean a more practical algorithm.

And it’s the same thing with P=NP. If it turns out that P=NP, it’s probably not the case that there’s this awesome, O(n^3) algorithm with tiny constants that breaks everything on a T-84, which would definitely have practical applications. P can be NP, but if the polynomial has a large degree, and by “large degree” I mean probably like, 6, a low constant subexponential is going to win on sizes people actually do computations with.

Again, I’m not trying to diminish the achievement. It’s an incredible theoretical result. But like most theoretical results in math, it doesn’t actually mean anything for the real world.

2

u/RedditTipiak 23h ago

Mathematicians are now "press enter" employees just like the rest of us.

1

u/Slow_Comfortable_128 17h ago

If there were real world consequences you wouldn't need the proof. You could just look at the real world consequences. (mostly)

48

u/No_Development6032 22h ago

There’s no moat as long as you own a country worth of gpus

9

u/Ok_Warthog6007 17h ago

and even that moat seems to be swum across in a few months, forcing you to use more gpus to deluge even more of the territory you've created until the whole thing is inundated and the project is sunk

232

u/Floch11 1d ago

Feels like this was posted just to say 'we solved it too, look what we can do' after OpenAI announced theirs 😀

33

u/llelouchh 23h ago

They disproved it on the 16th of October the exact same day that OAI disproved it.

16

u/Supersamtheredditman 18h ago

Everyone at the labs are constantly talking to each other. It’s not a very large community and they all live in the same city.

4

u/Hir0shima 20h ago

Random

144

u/ryan13mt 1d ago

It also means that OpenAI dont have anything "special" or "unique" and all the current frontier internal models are capable enough to do things like this

This also means next gen open source models will be able to do this as well

35

u/wyrin 1d ago

so true, once next gen open source can do this, that will lead to some Cambrian style explosion on proofs 😄

6

u/CallMePyro 14h ago

This would only be true if the next gen open models are cheaper than their closed source counterparts. https://matharena.ai/?comp=arxiv--september&view=problem

For example it seems that Kimi K3.1 is 4x more expensive (double tokens and double cost per token) than Sol 6.1 while being a lot worse at arxiv math. Open source needs to make significant gains in cost/performance if they want to compete with Anthropic or OpenAI in math.

17

u/xaranetic 1d ago

Now we need an explosion in human intelligence to understand, utilise, and predict the consequences 

24

u/wyrin 1d ago

Imo we are past that, just like majority of folks today don't understand financial markets, similarly in future majority will not understand all of this.. tomorrow's financial market might be out of grasp of everyone

35

u/socoolandawesome 1d ago

I mean did Claude solve all the other problems OpenAI did?

I feel as though you are making a massive generalization based on one, maybe two problems. Maybe it’s true, but I’m not sure there’s enough evidence to conclude that yet

4

u/ryan13mt 23h ago

I am generalizing but it still shows that Claude is capable of doing this as well

Not saying they are exactly at the same edge, probably one of them is being the other but they are still there and not months behind

4

u/Runfasterbitch 1d ago

I am become god

3

u/Melancholius__ 23h ago

...the slayer of all worlds!

2

u/fingertipoffun 20h ago

and humans have it coming.

15

u/Mistuv 1d ago

Let's not go that far with the last claim. This is mostly vibes, but it is where distillation works and keeps almost all of the benefits of the big model, it loses the bit of magic that allows the most complex problems to be solved.

I think it's telling that, for basically all normal people, Opus 5.5 is an incredible model. It gets the essence of what you actually want so much better than the other models. As far as mathematicians go, they still primarily use Astra with bit of Fable 5.1. Same goes for Sol 6.1. It's not like mathematicians have an unlimited compute budget. If these models were performing almost as well at a fifth/tenth of the cost, they would be using them instead.

Similarly in prior months, even though a lot of open-source models have reached Sol 5.6 level quite quickly, mathematicians and scientists still primarily used on Fable 5 and Sol 5.6. Even scientists in China used those models and while I don't think they would be forcing them to use the domestic models, there is a bit of nationalist pride, you would expect a lot of them to use something like GLM 5.3 instead if it was capable of the same, but it hasn't been the case for most (there have been a few but still). If Chinese labs will still rely on distillation plus + RL for the open-source models (same as american ones like Meta's new OS model), I would expect models next year to be a lot better at "ordinary" math, but unsolved problems which you could point the model at and expect a breakthrough would still remain the domain of the models that have not gone through the distillation process.

22

u/ryan13mt 23h ago

Ok, the gen after then

It's months away at this point, not years

1

u/ArrogantAstronomer 16h ago

Only people running even those open source models are those with a few spare HGX B300 clusters lying about.

I wouldn’t be remotely surprised to learn internal models doing newsfeed runs are running at full BF16 precision rather then the mixed precision models that are served

10

u/RabidHexley 20h ago

I mean, yeah, It's exactly this lol.

Considering I've seen people say OAI models are better at math and science due to their recent work, not surprising they may want to counter the narrative.

1

u/Glum-Objective3328 15h ago

Seems like Anthropic is going the route of patience so they can understand the result and verify it before making public announcements.

4

u/G0dZylla 1d ago

I wouldn't be surprised if anthropic planned on dropping this before IPO

2

u/n4te 23h ago

Yeah bro, I solved that one yesterday. Next!

1

u/Spunge14 21h ago

I mean that's...literally what it is.

1

u/hardinho 17h ago

Uhm yeah.. that's what it is and it's important for their IPOs

7

u/ShowerDear1695 18h ago

Did Claude come up with the same algorithm to disprove SETH/ETH or did it come up with a unique one?

13

u/DueAnnual3967 22h ago

If they really were sitting on it I do wonder... maybe internally there could be some discoveries that they may keep to themselves or sell to the highest bidder. Perhaps not now when they do not have much impact on real life but if they stumbled upon some discovery that makes fusion possible/cheap etc., I really doubt they will just go ''we give this to public'', they will definitely sell it people who can pay the most... Anything valuable top of the line models discover will be sold off to the highest bidder or used to improve models or labs themselves entering in some business where they see possible disruption

1

u/Disastrous_Elk_6 15h ago

Probably already happened .we screwed lol not lol Whatever went down with trump and anthropic last year.

43

u/t3hjs 1d ago

Man, anthropic needs better marketing. This js not the first time I heard of Levent's name, he was part of the team that got scooped on the Navier Stokes Milleniun prize solution 

He was already working on the Yang Mills quantum field theory problem:

https://github.com/ethanwsussman/Yang--Mills-LLM-experiment

and now OpenAI makes a big claim and everyone doesnt know Levent

58

u/socoolandawesome 23h ago

Levent was part of the team that didn’t actually solve the full navier stokes, whereas openai solved the full thing

6

u/t3hjs 23h ago

oh I dont deny OpenAI was the first to solve the full thing.

i just wished Anthropic threw the same amount of money,  publicity and compute to the problem. it's a small budget compared to the ~4B they spend on marketing. it's all a marketing exercise for OpenAI and Anthropic anyway

8

u/llelouchh 23h ago

Anthropic tries to work with the mathematicians and OAI just posts it lol.

14

u/Sensitive_Cell_119 20h ago

Both just post it, how many times has Levent slop dropped AI solutions in his twitter account? In the most quirky way possible as well lol.

10

u/kaaiian 22h ago

Honestly. OpenAI is doing the right thing here. No one should be gatekeepers of this type of knowledge. Anthropic has always given a “we are better than you” vibe. And this is no different.

3

u/llelouchh 22h ago

OAI said they wouldn't do it though (sebastian beubeck) but they did it anyway.

2

u/kaaiian 22h ago

You didn’t read the announcement yesterday? Or are you saying the original one on the 6th?

3

u/SnooDonkeys4126 17h ago

Yeah well MY uncle works at Nintendo too!!

4

u/Illustrious_Image967 23h ago

With a name like that I'm worried we will soon refute reality and find out the Simulation name is GTA 6 (Grand Theft Anthropic).

2

u/ArialBear 19h ago

So claude wants to race?

4

u/Gold-Direction-231 10h ago

Due to the nature of AI training, saying anything done by AI has no human input is fundamentaly wrong and misleading. This technology is amazing but this "AI vs Human" narrative is childish and ridiculous.

7

u/Eyelbee 1d ago

Openai possibly cracked it before 16th

3

u/FlimsyReception6821 22h ago

You snooze, you lose.

1

u/Hodr 22h ago

Do output tokens include thinking tokens?

1

u/huffalump1 19h ago

Probably

1

u/magicmulder 14h ago

Is this like Deep Impact and Armageddon, are they just copying what the other side does in the hopes to be first, fed by moles in the respective competitor's ranks?

1

u/Psychological_Bell48 14h ago

We need that 14m input token model to the public please !!!!

1

u/llelouchh 23h ago

On the exact same day is very suspicious. Oai scooping again?

1

u/Round-Walrus3175 20h ago

What does "no human input" mean with regards to this? Is it constantly on, giving random outputs until something comes up?

5

u/USERNAME123_321 18h ago

It's not random at all. 'No human input' just means researchers defined the problem and system, but left the AI in an autonomous reasoning loop to write code, run tests, and self-correct on its own. It's known as an AI agent. You can run these yourself locally using harnesses like Pi or DSH. I actually use local agents for coding projects all the time. Even if you don't code, it is sometimes useful for diagnosing and fixing PC issues.

1

u/Round-Walrus3175 18h ago

Ah, that makes sense. Feels more like "no human feedback" since defining the problem and the system (which was probably no small feat or prompt engineering) feels like a lot of practical inputs, even though it let it go from start to finish on its own.

2

u/USERNAME123_321 18h ago

Yep! In fact, that human feedback is generally referred to as "human-in-the-loop". If they wanted to be more precise, they could've said "zero human-in-the-loop". By the way, once the system is set up, you generally don't have to redo it, except maybe for certain specific tools. You just change the initial problem.

0

u/Big-Table127 23h ago

Did it steal from openai