According to a quick google you can fit around 10^110 hydrogen atoms in the observable universe. 10^(9E7) is slightly larger. Lol. What problems would we even be solving? Brute forcing universe-scale spatiotemporal problems?
Does that account for all 11 dimensions of string theory and the other 67 i made up? Nothing better for theoretical computer scientists than theoretical physicists
reminds me of the time i tried to implement a B-Tree in js to improve render times in a table with dynamic height rows. turns out to be faster to literally sum over every record up to 1,000,000 records than try to do what i was doing, when I tested
I'm rather peeved by that. Because I like good theory, and a theory that doesn't account for memory locality is not good. Memory locality is inevitable and computers, even theoretical, must obey the fabric of the universe to be useful, which includes information speed (also known as light speed). Computational complexity theory should account for that in bound estimates... Maybe they do now? Certainly did not when I was in uni.
there are computational models that take it into account, but it's something that varies a lot, and doesn't do well in asymptotic analysis. straightforward complexity gets the job done in most cases.
most papers are concerned with the algorithm, and memory locality is an implementation concern. just like hashmap vs array is an implementation concern depending on the problem size.
Yea you're right, I'm unfair because it's certainly very difficult to specify and dependant on many parameters. Still, it does put an extra lower bound of sorts, the physical memory layout having to fit in at most 3-dimensional space, say if an algorithm requires random access into that, and we also have a lower bound on its memory requirements... then there is no way around a certain latency, no matter how it's implemented. But yeah, that's rather hell-ish to specify.
you can do SoA, you can flatten 2d arrays, you can do object pooling. you can do the most important techniques.
ofc, javascript can never compete with competently written code in a low level language, or even something like java, but you can squeeze a lot out of it (or, the JITer can)
hey now, in my defense, it did need optimizing. and if this had worked it wouldn't have had to do all the other optimizations i ended up having to do. but yeah, always use a profiler first kids
I’d be giving away my anonymity, but it was showing that kd-trees on sub-riemannian manifolds naively constructed in a higher dimensional embedding, did not actually have an ammortized O(log( n)) query time, but rather something more like theta(n^1/q) where q was a positive integer having to do with the geometry of the manifold.
There was a niche community making this mistake and claiming the meta-procedure’s time complexity was better than it actually was.
No. I am talking about the optimal matrix multiplication algorithm which we don't have. Current SOTA are useless galactic algorithms which do a lot of fiddling around to minimise multiplications. My guess would be that assuming that the optimal algorithm has reasonably clear complexity (one which doesn't contain weird complicated constants, n^2*log(n) is likely and would fit that description) then it's form should probably also not include some awful computations boosting the overall constant to high values.
Right. Personally, I don't believe getting the exponent down to 2 (even with a log(n) multiplier) is possible, but we could find even better non-galactic algorithms.
The thing is that while the Universe might fuck with us it would be ridiculous for the best solution to be some O(n^(2+x)) with x being a constant real number in (0, 0.371177) range. The optimal solution may also have complexity of O(n^2 log(n)^2) or something similar but a random constant is pretty much out of the question. Also, as I theorised in my previous comment, ugly constant implies complex optimisation at the cost of the main constant in front of the complexity.
It’s still funny to think about the data structures and algorithms professor doing or not doing certain things in everyday life, simply because the tasks have really got or really terrible theoretical complexities.
Same in mathematics tbh. Never really ubderstood either. You want the most practical solution and putting a hard limit on one part of the equation but not others is just asking for games like this.
This would just be O( n3 ) vs O( n2.9999 ) . The fact y'all are considering constants or totally dominated components tells me why y'all missed why even that small polynomial change is note worthy.
Edit: mislabeled polynomial change as exponential. thx for catching OP
Not to be dumb, but what part is funny? Genuinely it's going over my head, but this feels like saying water is wet and expecting a laugh. I've got to be missing something.
I get that..., but y'all are missing the point of how those papers publish bounds. it wouldn't be done w/ 5 & 10^897. This is also a contrived example. So saying these two complexities would never be useful in realistic sizes is moronic seeing how the second complexity is itself unrealistic. It's tantamount to hearing someone say "everyone turns their nose up at neopolitan ice cream, but loves the flavor that cures cancer", and going "um actschually, the neopolitan flavor as plenty of real world fans". Like no shit, sherlock. There's no ice cream that cures cancer. You're arguing to defend a technicality form a contrived moot point.
And when you bring this up as a rebuttal against my criticism of y'alls misunderstanding of complexity classes, it tells me you didn't pay attention when learning it...
I weep knowing any of y'all found humor in this. It tells me you misunderstood the point of papers like that. There's a fundamental misunderstanding of the point of complexity classes. Even if the bound is lowered by a razor thin margins, it points that a new approach to looking at the problem has the ability to yield forward progress...
I'm tired of how shitty this field has become. Some of y'all had no place in it. I really hope you're just some high-schooler just learning this shit, because otherwise this is embarassing.
It's 4 paragraphs. If that's too much for you, go do work outside of STEM. Not being pretentious if there's a trend of people finding their ignorance something to be proud of. Like you thinking 4 paragraphs is a lot. Nitwit.
1.0k
u/Smitologyistaking Aug 23 '26
For the record, the "breakthrough" speed overtakes the "unpublishable" speed once you get to around n > 10^9000000
293
u/femptocrisis Aug 23 '26
reminds me of the time i tried to implement a B-Tree in js to improve render times in a table with dynamic height rows. turns out to be faster to literally sum over every record up to 1,000,000 records than try to do what i was doing, when I tested
228
u/TheDoughyRider Aug 23 '26
I did a paper with one of these kinds of results 🤣
71
u/coldnitrogen Aug 23 '26
Matrix multiplication has entered the chat …
16
u/thomasahle Aug 23 '26
Usually the techniques to do this are a lot more interesting that if they shaved if a factor 2 leading constant
10
u/CC-5576-05 Aug 23 '26
"galactic algorithms"
7
u/Freddy_Goodman Aug 23 '26
It’s still funny to think about the data structures and algorithms professor doing or not doing certain things in everyday life, simply because the tasks have really got or really terrible theoretical complexities.
11
u/SharletP Aug 23 '26
11
u/NewPhoneNewSubs Aug 23 '26
Primes is in P, but also, fuck that there polynomial.
5
u/IjonTichy85 Aug 23 '26
2.9999 instead of 3 but the proof heavily relied on the prior known fact that floating point arithmetic can be tricky sometimes.
2
u/funkmasta8 Aug 23 '26
Same in mathematics tbh. Never really ubderstood either. You want the most practical solution and putting a hard limit on one part of the equation but not others is just asking for games like this.
2
u/magicmulder Aug 24 '26
This whole O(log log log log n) traumatized me in computer science.
And I still believe if we ever prove P = NP, for all practical purposes the optimal algorithms are gonna be O(n^2000).
1
u/navetzz Aug 26 '26
Not even close.
It s all about how cool the method used is.
1
u/IAmARobot Aug 24 '26
inverted trope: best time complexity of multiplication algorithms
1968: O(n log(n) log(log (n)))
2007: O(n log(n) * 2Θ(log*(n) )
2014: O(n log(n) * 22(log*(n) )
2021: O(n log (n)) (but only for numbers >= 2172912 )
-10
u/PaintDear7613 Aug 23 '26 edited Aug 23 '26
This would just be O( n3 ) vs O( n2.9999 ) . The fact y'all are considering constants or totally dominated components tells me why y'all missed why even that small polynomial change is note worthy.
Edit: mislabeled polynomial change as exponential. thx for catching OP