CS professor Chris Okasaki, known for his book on purely functional data structures, also played board games and he came across this phenomenon. He realized that it could be modelled as a bipartite matching problem, and wrote a MUCH faster program to manage math trades.
https://okasaki.blogspot.com/2008/03/what-heck-is-math-trade...
I guess it can be made even faster now in theory.
It's mostly of theoretical interest except for some possible niche applications, I'd say. For a math trade type of problem, you'd just go ahead and use the old algorithm with an RNG.
Another famous result of this type was AKS primality testing. Randomized algorithms like Miller-Rabin were known for a long time, very reliable, and quite simple to implement, but AKS was an important theoretical advance because it didn't use random inputs. I think everyone still uses Miller-Rabin in practice.
For those unfamiliar: NC is the class of problems which can be solved in polylogarthmic depth with polynomial number of logic gates. It is unproven if NC != P similar to P != NP.
Wikipedia agrees :)
If you specify the exponent of the log, you get a different answer.
There is a beautiful proof of the disjunction between AC0 and NC showing parity cannot be done in AC0 using harmonic analysis of Boolean functions
That paper is in the wiki refs but Hastad’s original is from 1986
Which is still useful if you can prove a problem is in NC. It's just not quite as strong as people make it out to be.