Many years ago, on Boardgamegeek, there was a game trading system called "Math Trades", where participants would list a number of trades they were willing to make, and they ran some complicated calculations to figure out how to let as many as possible trade.
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.
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.
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.
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.
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