Are there any real life examples of growth that goes like n! ? The author brings up some vague example about networks, but I was expecting some real data and a simple plot.
In real life exponential growth is natural whenever something grows in proportion to its size.
Usually combinatorial explosion doesn’t really happen in real life because systems often only navigate a small subset of the total theoretically possible number of permutations.
Sure. Possible sequences of events in a concurrent or distributed system. Model checkers in languages like TLA+ have to contend with this. Of course in the real world only a single sequence of events actually occurs, but you have to know that your system works on that sequence whatever it is. The AWS TLA+ paper noted that at scale you’re basically guaranteed to eventually hit whatever combination of events blows up your system if such a sequence exists. Murphy’s Law of distributed systems I guess.
I'm not sure about combinatorial explosion, but Ray Kurzweil was talking about double exponential rate of innovation in the world, which may be similar. As a great example while transistor counts in processors still improve roughly with Moore's law, the cost of training a neural network to an accuracy is dropping faster than Moore's law because of algorithmic improvements.
Busy Beaver grows faster than TREE, SSCG and every other function in the fast-growing hierarchy. The latter are computable, while the former is uncomputable and (eventually) grows faster than any computable function.
Related, one of my goals for my mathematics thesis is to come up with a generating function series that can represent superexponential sequences. Right now, there are no generating functions for any sequences that grow faster than exponential, because the standard series we use, would not converge nomatter the coefficients.
"Facebook as a product doesn’t encourage you to add strangers as friends"
Yes, it does?? I don't do it, but every time I go there, it has a list of people who are either friends of friends or strangers that it's suggesting I add.
Perhaps there are people in the bowels of Facebook that are smitten with the concept of combinatorial explosion and have been thinking for years "any day now..."
It does on a superficial level ("here's a list of five people with buttons next to their names"), but it doesn't do it effectively. You're more likely to end up befriending a stranger using Tinder, or playing video games, or trying to pick up a new hobby, but Facebook doesn't enable those interactions very well.
>Facebook doesn't enable those interactions very well
I never looked to FB to enable making friends, I was dragged onto it because people I did meet elsewhere prefer to use it. So I don't know either how it's supposed to work or how it does work.
A weird (to me, probably not to a FB employee) thing that happened after my previous comment was...
I clicked on the "show me less" option next to "people you might know" (because it has been showing me former co-workers, who are fine people, but not friends, and I don't want them to be).
Then it collapses, but like three items down in the feed, there is a duplicate with the same people!
It also, along with Instagram, allows or supports fishing and hacking attempts from accounts and doesn't remove them - or most recently an account I reported on IG got an automated "review response" that due to too many reports they're not reviewing my report.
How we don't have laws requiring businesses do the minimum to keep users of their platforms relatively safe really highlights the inefficient-stagnant state of governance we're in in the west.
> But what if instead of looking at the number of users, we looked at the efficacy of users on a social network? We can then see how the productive power of a social network can indeed increase combinatorially, and to our great benefit.
I don't think this is "combinatorial growth" either? The number of possible networks is the same as the number of possible subgraphs, so should scale as 2^2n.
19 comments
[ 3.9 ms ] story [ 53.0 ms ] threadIn real life exponential growth is natural whenever something grows in proportion to its size.
Usually combinatorial explosion doesn’t really happen in real life because systems often only navigate a small subset of the total theoretically possible number of permutations.
More (sync) communications isn't always needed and doesn't unlock combinatorial explosion, otherwise we wouldn't actively try to limit meetings.
If you learn 1 new skill each day for a year...
then you will be able to apply the 365 skills you've learned in
365! = 2510412867 5558732292 9294437488 1202770516 5520269876 0797668725 9519390110 6138220937 4196660180 0900025416 9376172314 3609823286 6070807112 3369979853 4453679106 5387238359 9704355532 7409376780 9149142944 0864316046 9250745101 3484702554 6014098005 9079655410 4119549610 5311886173 3734351455 1719328276 0847755882 2916902135 3912347918 6274701519 3968085049 4072260703 3001246328 3988005504 8742799987 6690416973 4378610781 8534466796 6871511049 6538881301 3683619901 0529180056 1258445494 8864861768 2915826347 5641489909 8413806780 9999604687 4881467348 3734069935 9838791124 9959575845 3887361666 1533093253 5512568450 5604638873 8129702951 3811518614 1368892298 6510005440 9439430146 9924411255 5755279140 7604927642 5374025041 0391056421 9790032896 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 000000000
different ways!
[1] https://en.m.wikipedia.org/wiki/Kruskal%27s_tree_theorem
https://en.wikipedia.org/wiki/Stirling%27s_approximation
Gigantic fake numbers are rubbish (I believe that 110%), but saving work with approximation is cool.
What OP likely is referring to is Combinatorial explosion: https://en.wikipedia.org/wiki/Combinatorial_explosion
Related, one of my goals for my mathematics thesis is to come up with a generating function series that can represent superexponential sequences. Right now, there are no generating functions for any sequences that grow faster than exponential, because the standard series we use, would not converge nomatter the coefficients.
[1] https://oeis.org/wiki/Growth_of_sequences#Superexponential
"Facebook as a product doesn’t encourage you to add strangers as friends"
Yes, it does?? I don't do it, but every time I go there, it has a list of people who are either friends of friends or strangers that it's suggesting I add.
Perhaps there are people in the bowels of Facebook that are smitten with the concept of combinatorial explosion and have been thinking for years "any day now..."
I never looked to FB to enable making friends, I was dragged onto it because people I did meet elsewhere prefer to use it. So I don't know either how it's supposed to work or how it does work.
A weird (to me, probably not to a FB employee) thing that happened after my previous comment was...
I clicked on the "show me less" option next to "people you might know" (because it has been showing me former co-workers, who are fine people, but not friends, and I don't want them to be).
Then it collapses, but like three items down in the feed, there is a duplicate with the same people!
How we don't have laws requiring businesses do the minimum to keep users of their platforms relatively safe really highlights the inefficient-stagnant state of governance we're in in the west.
Remember, kids, growth for the sake of growth is the ideology of the cancer cell.
I don't think this is "combinatorial growth" either? The number of possible networks is the same as the number of possible subgraphs, so should scale as 2^2n.