r/compsci • u/cringevampire • 5d ago
All the complexity improvements released by OpenAI today
129
u/Zubzub343 5d ago
I've worked months on understanding the state of the art on the problem L=RL during my studies. If that's true, I don't know how to feel.
129
u/FriendlySeahorse 5d ago
You're not alone. A problem I worked (on and off) for 5 years was solved by AI a couple of weeks ago. It's a strange feeling.
My impression from my conversations is that most researchers are not happy about this. It's such a shame that huge breakthroughs are going to be made and it not be a moment of joy.
I predict that at some point in the next few years (months/weeks?!) P \neq NP will be proved by AI and nobody will be happy about it.
85
u/exosphaere 5d ago
P \neq NP will be proved by AI and nobody will be happy about it.
Even worse. They'll show that P \eq NP by contradiction. So you know it's true, but nobody knows how to construct an algorithm.
30
u/Aedan91 5d ago
Contradiction is my personal best case scenario in terms of equality. Knowing they are the same but not having an algorithm constructed. A lot of good things might come from that construction, but they come with far worse consequences attached.
I'd prefer to know they're different though.
19
u/LookIPickedAUsername 5d ago
That's not actually possible.
If P = NP then Levin's Universal Search runs in polynomial time, so we already know a (completely ridiculously impractical) polynomial time algorithm for all NP problems.
5
u/Gnafets 5d ago
It's actually a cute exercise to design a polytime SAT algorithm from just knowing that P = NP.
→ More replies (3)2
u/Glum-Objective3328 5d ago
Why is that bad at all?
5
u/swansongofdesire 5d ago
A lot of crypto algorithms are theoretically broken/unsafe and need to be updated asap, but it doesn’t help at all with other problems that should have benefited from the classes being equal (eg optimisation problems)
14
13
u/w-g 5d ago edited 4d ago
Kaczinski wasn't totally nuts. He percieved the situation correctly (about technology), but his reaction was bad.
I do hate AI. Really. It's not making people's lives better in any way. People are more and more exhausted, and they feel less related to their work (oh guess? Karl Marx said that about the industrial revolution - he called it alienation). I studied lots of things for 20 years, and now it's all worthless. AND it feels like there isn't much to do that will make me feel fine with my job.
3
u/goldenroman 4d ago
Marx also advocated for automation to minimize necessary labor so that people would be free to pursue what they wanted.
→ More replies (3)4
u/currentscurrents 4d ago edited 4d ago
No, Kaczynski was totally nuts. If we listened to people like him we'd still all be starving dirt farmers.
The industrial revolution has been the best thing for the common man in all of history. It brought us antibiotics, electricity, running water, refrigeration, air conditioning, automobiles, abundant food, affordable clothing, longer/healthier lives, and much more.
If AI will bring a second industrial revolution, I'm all for it.
→ More replies (1)→ More replies (83)2
u/ColdBuffalo2058 5d ago
Not happy with what? Then why were people working on these problems if they're not to be solved?
34
u/poralexc 5d ago
Sometimes the solution isn't the valuable part.
Like, you could 'solve' Fermat's last theorem with a yes or no answer or a counterexample like an LLM, but the real answer involved relationships across several recently emerged branches of study leading to entirely new fields of mathematics.
I'd be way more excited if these labs were willing to show their work.
11
u/shponglespore 5d ago edited 5d ago
It seems like maybe we need better ways to describe and quantitfy how good a proof is. In some sense, having a proof at all is showing your work. OTOH, I think most of us have had the experience of feeling unsatisfied by a clever proof because there's no indication of, for example, what intuition led the author to look for a specific contradiction. Most of the time what we want isn't just a proof, but a roadmap of how someone familiar with the subject could have invented the proof for themselves, and I don't know if a good term to use for that kind of document.
Edit: typo
3
18
u/riffraff 5d ago
may I suggest you read this article with many authoritative signatories
A Severe Misalignment of AI in Mathematics
TLDR: the process by which you find a solution matters somewhat more than the solution, and AI solutions threaten the whole math world.
→ More replies (5)16
u/Jackker 5d ago
It seems like a group of humans want problems to be solved by humans and not a 'non-thinking' entity.
→ More replies (2)7
u/rog-uk 5d ago
Also employment, if it can attack maths or create new maths that no human can understand where does that leave research academics?
→ More replies (10)10
u/danby 5d ago edited 5d ago
Really importantly, if they don't do the work to translate the proofs in to legible form and confirm they are actually correct then they aren't really doing research and they aren't producing anything that other researchers can make use of.
But this would require they had a team of mathematicians/logicians to work through these things but that would also take time. It would delay these announcements by months (maybe years for some proofs). They'd rather squirt out an unverified answer for the sake of the press today than actually contribute fruitfully to the research community. And no doubt that kind of glory hunting puts many researcher's noses out of joint
5
u/NoteVegetable4942 5d ago
If it is not useful, then why are people upset? Surely if nothing of value was created, then nothing has been taken from mathematicians?
2
u/danby 5d ago
Read my last sentence again.
Though I will say if a problem is said to be in a solved state it will likely prevent you getting any grant money to study it or tidy up the solution in to a useable state so that would also be quite annoying if you work in the field.
→ More replies (10)→ More replies (1)3
u/ama_singh 5d ago
It's about the journey, not the destination. Think hard about whether you'd really want an all intelligent AI.
22
u/AffectionateWalk19 5d ago
Dude, L = RL actually shocked tf out of me. I've studied this problem so much and I planned to study the problem in graduate school. Hopefully the proof yields interesting maths. I started reading it a bit ago but the article is rather poorly written.
→ More replies (1)14
u/LifeInJapan1999 5d ago
You don't need to feel anything, you need to go switch to being a plumber, obviously.
It's important you do manual labor so ChatGPT can do all the discovery, art, and creative thinking we used to spend all of our time doing.
2
u/Smallpaul 5d ago
Not a single mathematician has lost a job yet and software engineer job growth continues as well. Let’s put a pause on the doom and gloom until the AI is actually able to replace us.
→ More replies (3)1
u/Chemical-Year-6146 5d ago
Did you see Astra fully control a robot, albeit slowly? Yeh, plumbers have about 2 more years than the rest of us.
→ More replies (1)3
u/golfstreamer 5d ago
Do you think the problem isn't AI but the culture of math itself? Why is that when one person proves a result like L = RL everybody else stops working on it? Like different approaches couldn't yield new insights?
I'm not an academic mathematician but that never really made any sense to me.
3
u/ExistentAndUnique 5d ago
Well usually for big problems like this, the point is that all previous approaches didn’t quite work. But the one that does generally provides some new insight or method that people use as inspiration for other projects. The problem is that if nobody understands the proof (because it’s incomprehensibly written, even if machine-verified), this doesn’t happen
→ More replies (1)4
u/Smallpaul 5d ago
If the computer proof is literally incomprehensible, and the real value is in the process of a human making the proof then the real problem is still open and a human can still get a Fields medal for it. What they will not do is waste their life trying to prove something is false which is true or vice versa.
Or…conversely, if the AI proof is difficult to read but comprehensible, then it contributes to the state of the art and someone just needs to dig in and comprehend it. And they should be rewarded for doing that.
2
u/danby 5d ago
Depends on the problem. In some case a new proof is the only approach or application of current maths that works. So until some new maths/techniques show up there may not be point on continuing to work on something, for now.
Often times an important proof delivers new techniques and insights that open up other problems and sometimes open up entire new branches of maths. So people start building new things on top of the proof.
But there are things where people might be unsatisfied with some proof and will work to simplify/rationalise it in some capacity.
173
u/Decahedronn 5d ago
Kappa 2-182 lol. Surely there's a bug in the Lean or something
119
u/FriendlySeahorse 5d ago
From what I can see, there is no lean proof for that one (https://github.com/openai/math/blob/main/CONTENTS.md)
Just, you know, a 70 page paper which I'm *sure* has been checked for correctness. (/s)
74
u/AffectionateWalk19 5d ago
The L = RL result is 100 fucking pages long LMAO. I feel like I'm getting fucked raw no lube due to the lack of exposition. The paper describes error correcting codes like a goddamn alien.
42
u/redditboy117 5d ago
And we are forced to believe it, to check it and most likely they won't announce the number of papers they needed to correct. The numbers, whether correct or not, are part of their game.
26
u/splendiferous-finch_ 5d ago
By the time the analysis and correction happens the media would have already moved on to something else.i agree
24
3
26
u/_choam_ 5d ago
If they are going to dump so much, we might as well automatically dismiss it unless they provide a mechanical proof (lean or whatever prover they use).
Would be good for finding bugs in theorem provers as well i guess.
15
u/Smallpaul 5d ago
They should actually provide both a Lean proof and a human verified “explainer” for each one.
3
u/DailyThreadBot 5d ago
Isn't the explanation a job well-suited for the general mathematical community? OpenAI doesn't have the expertise, or even the incentive, to understand all of these proofs
9
u/Smallpaul 5d ago
Why can’t AI do it? I’m not joking: if they want us to be impressed by the prowess of their AI then that’s part of it. AI should be able to explain the work of AI.
Human mathematicians should be paid to review the explanations and say where they don’t make sense or are confusing.
2
u/jeffgerickson 5d ago
Whether AI “should” be able to produce human-mathematician-readable expositions is beside the point. For these results, OpenAI’s internal model didn’t, which rather strongly suggests that it can’t.
3
u/Smallpaul 5d ago
Not really. Let’s imagine that it doubled the cost of production to have a swarm of agents produce the exposition. They might just choose not to do it.
→ More replies (3)7
u/OkFly3388 5d ago
Mechanical proof is not guarantee to be actually logical, because if some initial constraints was wrong, it can happily verify your "proof", despite it having critical logic flaw
→ More replies (1)
34
u/Winter_Ad6784 5d ago
O(2^(n/2)) -> O(2^(n*0.49)) is kind of a slap in the face lol
15
u/cringevampire 5d ago
https://x.com/konstiwohlwend/status/2107872422825537599
this seems to explain it really well
2
u/fiftyninefortythree 4d ago
ok. so now i fail to understand how this is an improvement? like how is this not hallucination?
2
u/_Super_Straight 5d ago
How big of an impact does that 0.01 makes?
14
u/Winter_Ad6784 5d ago
its actually important proving that the previous amount wasnt a lower bound and theres certainly better ones but just the simplicity of the 0.49 as opposed to to 0.5 is funny
367
u/Sniffy4 5d ago
great, has any human actually verified the chain of logic of these claims? I've worked with AI enough now to know this is an absolute requirement.
112
u/Better-Lock-5355 5d ago
the proofs are lean verified, but have not been peer reviewed yet
183
u/Gnafets 5d ago
False! Many of these have not been lean verified, including L = BPL!
8
u/Ok-Wait-8465 5d ago
Ah I misunderstood and thought they were all Lean verified. Did they have humans check the manuscripts then? I have a hard time believing humans checked all 700+
8
u/Gnafets 5d ago
It appears that the *only* paper that was semi-checked and edited by a human was the Quasi Riemann Hypothesis. Everything else seems to have had no human scrutiny (until now)
11
u/Ok-Wait-8465 4d ago
Looks like they’ve made a few updates
https://github.com/openai/math/blob/main/history.md
They withdrew three manuscripts due to an error in one underlying proof for all of them and say they’ve checked about 40% now
Interestingly another group released this on arxiv
https://arxiv.org/pdf/2610.08144
It doesn’t argue the Lean proofs are wrong or anything, but it does put some interesting perspective on the translatability of a natural language proof to a Lean proof with the same logic
It’s interesting they are approaching it this way. It feels very tech company which is not what I’m super used to in math/tcs
7
u/Gnafets 4d ago
It is particularly hilarious that this happened. I'm now seeing people say on their hindlegs, "well, human mathematicians make mistakes too so it's totally normal!"
It is absolutely antiscience what they are doing. If they had any care at all, they'd make sure everything is Lean verified and *both* the natural language and lean checked.I saw this paper as well. It addresses what mathematicians have internally known for a while: it is uncomputable in general to make sure an autogenerated Lean statement semantically maps onto a natural language statement. It is why the current set up CANNOT stand, and we need the Lean verification to be presented side by side with the natural language, with the same structure.
5
u/Ok-Wait-8465 4d ago
Yeah at the moment there are a ton of issues and this is kind of a weird way to treat math. (I saw someone else referring to it as “dropping raw data” which I think does happen sometimes in other fields so maybe we’re getting a taste of other fields? It’s also a very software/tech company mindset rather than the more careful releases we’re used to.) I think a part of why it feels different when they release a wrong proof than when a mathematician releases a wrong proof is the amount of human effort and checking that went into it. I’ve made a mistake of submitting something with a fatal error to a conference and it’s extremely embarrassing to do so, but I submitted it in good faith and believing I’d done my due diligence, not just slapping something together which is think is what’s particularly upsetting here. At least they did acknowledge their mistake when corrected though
I do think it’s done much more in the last 6 months than I ever could have imagined last April though, so I’m still concerned about what the future may look like, as it seems likely to somewhat soon figure out how to write actual human readable correct proofs. And I guess separately and likely using a different train of logic write correct Lean proofs. I do strongly prefer human readable/checkable though
→ More replies (1)3
u/Ok-Wait-8465 5d ago
Wait not even Unique Games? That’s crazy to put that out with no scrutiny
9
u/Gnafets 5d ago
Unique Games had a Lean formalization at least. Per a Scott Aaronson blog post that just dropped, his wife Dana Moshkowitz said the (natural language) paper is incomprehensible and poorly written. There is going to be a truly terrible future effort of checking that the lean translations of the natural language statements are actually correct
5
u/Ok-Wait-8465 5d ago
It’s interesting they’ve gone with a completely different philosophy than Anthropic which paid Josh Allman and Virginia Vassilevska Williams to write up their 3SUM and APSP proofs in a more readable way
2
u/Gnafets 5d ago
The Anthropic approach is certainly better by a lot, but still very morally dubious. I think Josh and Virginia should publicly disclose how much Anthropic paid them and the details of their contracts.
→ More replies (3)20
u/BeautifulMortgage690 5d ago
Sorry I just had to say this: What's BPL factorial?
26
u/danielbenedi6 5d ago
BPL is Bounder-error Probabilistic Logarithmic Space. This are the problems that have an algorithm to decide it using logarithimic space and if they answer is "yes" it will be correct at least 2/3 of the time or if the answer is "no" it will be wrong at most 1/3 of the time. If I'm not wrong, L = BPL implies that all the problems that are decidable with a randomized algorithm in L are also decidable with a deterministic algorithm in L. I hope it wasn't a joke about they writing with exclamation mark
17
u/BeautifulMortgage690 5d ago
It very much was a joke about them writing with an exclamation unfortunately :(
10
4
22
u/js49997 5d ago edited 5d ago
Also lean as a few soundness bugs AFAIK so "lean verified" should still be taken with a grain of salt. (https://daily.dev/posts/postmortem-for-kernel-soundness-bug-14576-leonardo-de-moura-1g69fps54) Also see paper on mistranslation of NL in to lean https://arxiv.org/pdf/2610.08144 which could be another way "bugs" creep in.
→ More replies (1)9
u/Smallpaul 5d ago
Lean had…past tense…a soundness bug in its kernel. This was news because it is so rare to find one and because of the way that it was “unveiled” by publicity hunters. A different Lean kernel had a different bug (which was already fixed by the time the proof arrived). By threading very carefully an AI could exploit both bugs to make a proof that seemed (past tense) to validate.
I would still trust Lean to verify a proof before I would trust any specific human being. Human proofs can go through multiple rounds of peer review without anyone noticing an error.
The chances of something like that happening with Lean are minuscule. The proof would look funny. Another AI could detect its weirdness. It would be detected when Lean fixed the bug.
14
u/js49997 5d ago
I'm not here to bash on lean. and yes I would trust lean over 10 humans. I'm just saying it has had bugs so assuming there aren't others and thus everything it spits out is 100% might not be a good idea. I have no evidence the lean proofs are buggy, just saying it has a none zero probability.
3
u/blakeh36 2d ago
as a theoretical computer scientist, I definitely know people I'd trust over an AI lean proof. It's extremely insideous, and I've also witnessed my fair share of "wrong" lean proofs
→ More replies (1)→ More replies (1)14
u/Axman6 5d ago
Wasn’t one of the recent “breakthroughs” relying on a bug in Lean’s type system implementation that’s now been fixed?
47
u/dualmindblade 5d ago
No. It is traditional to announce the discovery of a soundness bug in Lean by proving the collatz conjecture.
10
u/Smallpaul 5d ago
I actually don’t think it is traditional. It’s traditional to prove that true is false.
Proving the Collatz conjecture was a brilliant and infuriating way to get publicity. And the fact that we are still explaining it months (probably soon years) later shows how brilliant and infuriating it was.
3
→ More replies (7)7
u/Smallpaul 5d ago
Lean verification is far superior to human verification, although the combination of the two is best overall.
18
u/Tunisandwich 5d ago
Oh thank god, I needed to do 10,000,000,000,001 Fourier transformations but I only have time for 10,000,000,000,000
62
u/astrolabe 5d ago
The next ten years are going to be interesting. If we survive them.
3
u/NoNameSwitzerland 5d ago
Wasn't there just the prove released that surviving is boring?
→ More replies (1)
13
u/lkfavi 5d ago
Anybody ELI5 what this means for someone that looks at this formulas and understands 5% of them?
10
u/yjlom 5d ago edited 5d ago
AI came up with a bunch of new algorithms that are marginally faster than the state of the art when working with gigantic amounts of data (they're probably much slower on typical workloads, but I haven't had the opportunity to test it for myself).
(In big O notation, n refers to the size of the input, and the formula refers to the degree of the main contributor to the increase in computation steps for large n (so if it takes
2 n² + 4 n + 5steps to compute an answer, we say the algorithm is O(n²) because the time will eventually be dominated by a second degree polynomial, or if it takesn / 2 + 9999999999999999999999999steps to compute, that's an O(n) algorithm)).→ More replies (2)6
u/FivePointAnswer 5d ago
Let me offer a slightly different take on each of these: for each problem, AI accomplished a new better bound that undoubtedly someone probably could have gotten a PhD for, and I. The process maybe there made other incremental PhD level improvements along the way. Furthermore whatever was the state of the art had been studied considerably and no human had yet published that they had figured out what the AI did. It is additional evidence of approaching human superiority in the algorithmic domain. (Before the rocks come out I said approaching).
36
u/Zafrin_at_Reddit 5d ago
Alright. Alright. Hold on a second. With kappa = 2^(-182) in the integer multiplication, it sounds more like a "gotcha" moment. Cool you disproved it, I guess? Similarly to the FT piece with slightly higher delta of 10^(-13). Could anyone elaborate?
29
u/ellisonch 5d ago
It had been conjectured that you couldn't do better than nlogn for multiplication (Schönhage and Strassen in 1971). IIUC, we only figured out how to get as low as nlogn in 2019 (Harvey and van der Hoeven).
So, this result proves that conjecture false.
→ More replies (29)→ More replies (2)2
u/ThrowRA182790 4d ago
FWIW integer multiplication has now been optimized down to 2^(-15) https://github.com/CrocSwap/integer-mult-bounds
→ More replies (1)
31
u/AuDHD-Polymath 5d ago
The integer multiplication one has me absolutely cracking up. They improved n log n to n (log n)^0.999999999999999999999999999999999999999999999999999996
And you would need be multiplying at LEAST 2^2^6e54 bit integers before you could see any clear improvement. For reference, there are only 2^2^8 atoms in the entire observable universe.
46
u/ChiaraStellata 5d ago
The importance of this result, for complexity theory, is that it means all of our attempts to prove the n log n lower bound for integer multiplication were in vain. It cannot be proven, because there exists an algorithm faster than n log n. Which raises the question, how low can you go? What is our new suspected lower bound? How do we come up with it?
7
u/BrixtonTonaBrix 5d ago
Do we know whether a faster algorithm actually exists? If so, do we know what it is? If we don't, how do we know they didn't just find some way to cheat the verification?
→ More replies (18)12
u/brikky 5d ago
Their work obviously needs to be checked and go through review, as any other discovery would.
It's very unlikely that they found a way to cheat in lean though, it's quite well formalized. Not impossible, but unlikely. More likely that their prompts got misinterpreted when converting to lean, and that's how any issues would creep in.
→ More replies (1)→ More replies (7)2
u/mesohohnee 2d ago
In a way, it's like it found a counter example. Thereby disproving n log n is the lowest bound
5
u/brikky 5d ago
Several of these are not changing the big O run time, because big O of x1.999999999 is still big O of x2.
It's a stricter big omega/big theta.
→ More replies (13)3
u/Glum-Objective3328 5d ago
We have to start making matter yesterday if we want to capitalize on this result
2
1
u/WittgensteinsPoker-2 5d ago
To be fair, these kinds of numbers have had import in certain problems going back to Colossus
→ More replies (8)1
9
u/Smallpaul 5d ago
What I mean to say is that if the value proposition for the field changes then grant makers can change what they fund. Proofs got grants because it was what we valued in the past. Explanations may get grants in the future.
→ More replies (4)
8
u/Hoes-Love-wF 5d ago
As someone who’s currently taking algorithms. Im upset to find out there’s more time complexities than the basic ones im learning now
→ More replies (2)3
u/Defiant-Plantain1873 4d ago
Time complexities are like pandoras box, once you realise there’s loads of them, you will hate yourself
8
136
u/aliocha 5d ago
OpenAI, and LLM in general, really spoiled the fun of math and computer science. It really become a pay to win game
68
u/ParkingStaff2774 5d ago
In general, life is pay to win. You didn't get to drill down into math like these unless you had loads and loads of time on your hands by way of someone or something funding you.
→ More replies (2)9
46
u/Flaccid-Aggressive 5d ago
How much do you think it costs to spend 20 years of your life working on one of these problems?
27
u/Siech0 5d ago
Journey over destination. Some people find meaning in putting in the work and enjoy the process behind it.
17
u/NoteVegetable4942 5d ago
Someone is paying for it. These problems were not going to be solved by hobbyists.
11
u/nuggette_97 5d ago
No one is stopping you from not reading the proofs and continuing to work through them yourself.
This is a ridiculous statement. This is like saying lebron james ruined the journey of basketball or stockfish ruined chess.
7
u/ewheck 5d ago
No it would be like saying the NBA replacing players with androids ruined basketball
→ More replies (4)4
u/garloid64 5d ago
So your contention is that mathematics is just a game we play for fun? None of this stuff could ever be useful in the real world, so we should just prioritize the entertainment value instead of actually solving problems?
→ More replies (1)→ More replies (7)5
→ More replies (1)2
u/CMDR_Makashi 5d ago
100% agree. These people are just exposing their privilege that they have this time to dedicate in the first place
4
u/rog-uk 5d ago
They were also the people that taught the folk doing the maths that underpins AI/ML...
1
u/CMDR_Makashi 5d ago
Yeah totally and their contribution was vital and for that we should all be grateful. That doesn't mean we shouldn't continue to progress technology though.
3
u/puppySaturation 5d ago
Well you still get to learn about it's findings. I'm interested in the improvement of FFT, it will take me a while to get through that paper though. Maybe it's adjusted to some high level mathematical jargon, but for me it's thick as a bowl of oatmeal.
7
u/golfstreamer 5d ago
I just don't agree with this at all. I don't think rapid results like this can happen forever. It's not omnipotent. What about the thousands of other problems it couldn't solve? This raises the bar for how difficult future conjectures will be.
3
u/Infamous_Mud482 5d ago
Difficulty? We're talking about looping swarms of agents 24/7 until some signal for a workable path surfaces. What's fun/interesting about the field being more inaccessible than it's ever been? Nothing was ever stopping you from picking up some textbooks before and learning all the relevant theory to work on something interesting besides time, which is a very real barrier, but time is something everybody does have and just chooses to use differently outside of work.
→ More replies (15)7
u/VayneFTWayne 5d ago
It's going to unfairly keep advancing even if it gives you existential ontological dread.
→ More replies (1)2
u/Zealousideal_Elk3863 5d ago
ts gonna be the end of western materialism frfr. The things that made us humans special have is being appropriated by some models(yeah the art is still ass but who knows what the future holds). Everything you revered has been ussurped in a sacrilegious way.
Modern man has forgot he worships humanity, and that creates a mental dissonance when presented with threats such as these, as can be seen by the countless discussions on this topic on reddit.
When you forget who your god is you are going to be living a very confusing life frfr
2
2
u/PersonalDatabase31 5d ago
It already was lmao how many kids had Erdos as their teacher at 10 years old like Terence Tao.
2
4
u/PrashantThapliyal 5d ago
Aren't those results freely distributed to everyone?
4
u/MartinLik3Gam3 5d ago
Yeah but THEY don't get to brag anymore how THEY solved some math problem lol
2
u/nxy7 5d ago
The funny thing is that those results by themselves are useless. I don't even know what 90% of them mean. You need someone educated to understand them and how they can be applied.
→ More replies (1)→ More replies (11)-4
u/chebum 5d ago
I almost don’t code anymore and I’m extremely happy. Analysis, experimenting , planing and debugging are way more interesting activities than writing code by hand.
19
u/Agreeable-Cell4007 5d ago edited 5d ago
AI also does all the others things better than you genius.
→ More replies (3)9
u/golfstreamer 5d ago
As a programmer who's working with AI everyday I just don't think so. If you have clear unambiguous specification it's really good at meeting what you said. But translating a real world problem into an "unambiguous specification" is a what a lot of programming is about.
And I've seen it make absolutely _wild_ mistakes. Just yesterday I had it restructure a one custom data structure. And it decided to completely destroy another part of the algorithm.
I think people here "AI is better than debugging" but don't really describe all the dimensions that statement can lie on. Like better at identifying a particular bug causing a crash? Yeah. Better at identifying systemic issues limiting the ability of your program? I don't think so.
52
u/arbeit22 5d ago
From n × log(n)1 to n × log(n)0.9999999999999
Congrats! /s
In all seriousness, some of these look nice but others, like this one, just feel like a joke
55
u/lurking_physicist 5d ago
If true, it should be read as "one can do better than n log n". Now that this natural barrier has been broken, there is the question of how low one can go. It's not useful in itself, likely involving astronomical constants (I didn't even open the result, it's just how those things usually are).
13
u/Ae4i 5d ago
Opened the link and was satisfied seeing the 10-34% improvement of mentioned there
14
u/lurking_physicist 5d ago
Yeah, same energy:
"this minuscule improvement breaks through both a theoretical logjam and a psychological one"
→ More replies (1)37
u/StanleyDodds 5d ago
It was a somewhat serious conjecture that n log n was optimal for multiplication, so any improvement on this is important. The exact constant is less important. Further improvements can come later; this shows that it's not futile, and maybe how to go about it.
2
9
u/Truntebus 5d ago
They got the old upper bound for the matmul exponent wrong, yes? Last I checked it was omega < 2.371177.
12
3
u/wercooler 5d ago
The integer multiplication and Fourier transform improvements have got to be in the running for the smallest improvements to a bound ever, right?
1
1
→ More replies (10)1
u/Proper-Ape 2d ago
And none of these are confirmed yet. AI is really good at hiding subtle mistakes to game benchmarks while still looking right. Only because a lean proof worked doesn't mean the lean proof was set up correctly.
We have to take all these with a huge grain of salt until then.
3
u/green_meklar 5d ago
I love how the difference between log(N) and log(N)1-K is so small, and yet so big. Cool stuff if it pans out.
6
u/Bitter-College8786 5d ago
So, can we expect that games will run faster now on my laptop?
17
6
u/Legitimate_Concern_5 5d ago
Given the FFT performance went from O(n (logn)**1) to O(n (logn)**0.9999999999999) I'd say probably not
5
3
u/Exzakt1 5d ago
No, all of the optimizations found here are so microscopically small that even if you ran a simulation of the entire universe down to every quark, these optimizations would not change anything. I'd argue that why this actually matters is that it shows people that the nice numbers we thought were bounds for stuff are actually not accurate, which makes it pretty likely that they can be pushed further. If we can go from 2 to 1.9999999999999...6 we can probably get that down to 1.999999999999...5 as well.
1
u/PM_ME_UR_FAV_THINGS 5d ago
No, that’s not really how this works, this is asymptotic complexity, as in the growth of the solution when compared to the growth of the problem pushing out into infinity.
Generally speaking these marginally better asymptotic complexity algorithms have far higher overhead than their simpler counterparts, especially when considering what the hardware architectures’ operations are limited to/accelerated for.
So when we talk about real use cases, these algorithms are seldom used. Optimization in that space is more around the machine(and the proper utilization of it) rather than the fancy algorithm.
1
1
1
u/AcanthopterygiiIll81 1d ago
They're probably going to get slower the more people vibecode lol
→ More replies (3)
3
u/shponglespore 5d ago edited 5d ago
Regarding the proof that multiplication isn't O(n log n), I'm reminded of that fact that a lot of "proofs" in computer science assume all arithmetic is O(1). I would hope that the real proofs (not the versions shown to undergrads) consider the true bounds for arithmetic.
I think there's a gap in how programmers think about big-O notation and its formal definition. We normally only think about a large n in terms of the word size of the hardware we're working with, so, for example, addition looks like O(1) when you assume n < 264. An improvement that's only relevant when n >> 264 isn't of any practical use, but it's formally correct because placing an upper bound on n is something you specifically can't do in big-O analysis; if you use any upper bound at all, then all operations would appear to run in constant time and space.
I wonder if it would be a fruitful use if AI to look at computer science proofs and see which ones still hold up when you properly account for arithmetic operations taking more than constant time. We might find a lot of things we consider O(n) are really more like O(n log log log n), etc.
→ More replies (8)
2
u/Electrical_Crow_2773 5d ago edited 5d ago
Wasn't maximum matching already (n+m)1+o(1\)? With that fancy but impractical almost linear maxflow algorithm that has existed for ages
Edit: if someone knows how to make the closing parenthesis not look weird, please tell me
Edit2: Thanks, TSM-
2
u/TSM- 5d ago edited 5d ago
abc(def\)
abc^((def\))(n+m)1+o(1\)
(n+m)^(1+o(1\))you have to use backslash to escape the first closing parenthesis. It appears to hold up after refreshing the page. This is because the brackets are used to "contain" the part that's being superscript, but when you end with `))` it picks up the first one as finishing the superscript part and then the second one is not superscript.
A similar thing happens to links that contain certain characters. Note that if you use rich text editor and edit a comment, it won't keep the backslash in.
1
u/Ok-Wait-8465 5d ago
Is it max weighted matching? The max flow algo has a log U term where U is the max capacity. I’m also curious if this is combinatorial whereas I think the others tend to be somewhat numerical. (I haven’t read it so no idea)
2
u/Electrical_Crow_2773 5d ago
I was talking about this paper from 2022 https://arxiv.org/abs/2203.00671
3
u/Ok-Wait-8465 5d ago
That abstract assumes polynomially bounded capacities. I’m not sure what the OpenAI really claims but to my knowledge if they were able to show it without dependence on U that would be novel
→ More replies (3)
2
u/gomorycut 5d ago
the textbooks full of statements like "Tarjan improved this to [something involving epsilon]" will be full of "this was improved by OpenAI to [blah blah]"
2
u/itwrong 4d ago
The matrix multiplication bound can be expanded to any field using, as far as I understand, pretty simple techniques. My Codex did it within 6 minutes, while I was using it to understand why the result had a dependency on the field in the first place.
So, ω ≤ 9/4 = 2.25 for any field. Proved in Lean (https://github.com/selanavot/matrix-multiplication-all-fields).
→ More replies (4)
2
2
u/MelonYellow299 3d ago
The matrix multiplication algorithm seems interesting. Does it give an algorithm? Ex: could a program implement their construction right now and see the improvement?
→ More replies (3)
1
u/Shot_in_the_dark777 1d ago
Ok, now THIS is what I am talking about when I ask for ACTUAL resilts that benefit us NOW! Maybe some of those improvements are miniscule, but matrix multiplication going from 2.3714 to 2.25 or less in a world of computing is absolutely legendary! This is where the research should be! Stop getting those nano improvements for integer multiplication and keep pushing the matrix multiplication. It really feels like we can get to w=2.
4
3
u/SafeSemifinalist 5d ago
Is there any repository with actual implementations? do you think that this will be of practical use or theoretical interest?
12
14
u/FollowingHumble8983 5d ago
All theoretic. Any implementation is going to be magnitudes slower than existing ones until you get to impractical scales. But its very interesting and breaks a lot of assumptions in theoretical computer science.
5
u/AffectionateWalk19 5d ago
If valid it could have interesting implications for error correcting codes which are both practical and theoretical objects.
2
u/Lustrouse 5d ago
Matrix multiplication seems like something with actual implementation. This is an important improvement for many fields.
3
u/Own-Tangerine4564 5d ago
The numbers are from algorithm analysis, matrix multiplication is still n^3 in the real world.
If they found a way to make it ^2.25 without a big constant it would make them the most valuable company on earth and they wouldn't be releasing it lol
1
1
1
u/rij1 5d ago
I personally view the one on existential first order theory over the reals (and the exist-for all version) to be quite important too from a complexity point of view. Even though it was proved nearly 50 years ago, it still feels surprising that it is below EXP time and now it is even below PSPACE (even if it has felt like that was getting closer for some time). Note, instances of the problem can have a unique solution in which the numbers used are double exponentially large (e.g. iterated squaring would be an instance) AND we can decide if there is a solution in, now, less than PSPACE. It is a useful way to get complexity upperbounds in areas that requires solutions to complicated polynomials instead of trying to do such directly.
1
1
u/Zafrin_at_Reddit 5d ago
Brother please me all you wish. Unless the solution is proven and/or peer-reviewed (which it is neither at the moment), this might just as well be a random noise that could have been spat out by LLM in the 100+ pages long proof. It would not be the first time OpenAI claimed something a “solution”.
1
1
u/InNoNeed 5d ago
I read those and thought they were jokes poking fun at the marketing of AI doing all this incredible stuff. This seems very marginal and not really usable
1
u/Ok-Wait-8465 4d ago
Looking at their release statement it’s not clear if they mean weighted or unweighted but it seems they’re talking about general graphs not bipartite graphs like I was thinking. (Result 120 in their main release paper)
1
u/Secure-Tradition793 4d ago
This looks like a new grad throwing out 50 code reviews to the team for 1% performance gain in synthetic tests.
1
1
u/kingofallbearkings 3d ago
We are headed to where Sam wanted, intelligence on tap. Wanna solve cancer, $15million and 2 weeks of compute. Intelligence as a utility, reminds me of the whole cloud computing lifecycle
1
1
u/DoxxThis1 3d ago
#109 and #130 could be due to a floating point rounding bug in Lean. Source: just look at it
1
1
u/Risc12 2d ago
While this all seems very impressive, I’m not smart enough to judge it, and I don’t trust AI enough to 100% believe all of these are correct.
LEAN proofs are internally consistent and proven, but wtf is in there is hard to comprehend.
Until someone that actual understands math understands what is vibe-mathed can hype me up im lukewarm to this.
89
u/kaereljabo 5d ago
That unit job scheduling, yes it's polynomial, it's O(n150020 )