The NxM problem
Settlers of Catan is a great game. It doesn't have a boring 2-hour runout like Monopoly. There are usually 2 winning contenders for the length of the game. This post isn't about Catan. It's about the NxM problem (I pronounce this 'N cross M'). Let's start with a hexagonal example.
Direct trade in Settlers of Catan
Catan uses a trading mechanism to get resources you don't otherwise have access to. You want sheep? Lisa has sheep but it will cost you some wood. You're low on wood but Jeff can help you out for that pile of ore. Y'all strike a deal. You trade ore to Jeff in return for his wood, and then you hand this wood to Lisa for her sheep. With all this you draw a victory card which turns out to be useless because you already have the largest army and no one else is shooting for it.
Catan resource exchanges are an example of direct trade. There is no common medium of exchange, like money. In Catan this makes for a fun game. In the real world, having to write 3 lines of code in return for a cheeseburger would get really tedious. Unlike code or clay, a cheeseburger worth of money easily fits in my pocket. If Catan used money the new trade graph would look more like this.
Adding money to the markets of Settlers of Catan
By adding the
money node as a proxy for trade, we've removed 5 edges from the graph. Adding a 6th resource, rice, to the Direct Trade model requires N-1 edges to be added, one for every other resource. Adding a 6th resource to the graph using money requires only one edge to be added.
Money is one example of solving the NxM problem. The NxM problem presents itself with a bunch (N) of interconnected graph nodes, where adding a new node to the graph means adding a bunch (N-1) of new connections between the nodes on the graph. Solving the NxM problem adds one new node that can connect to all the nodes on the graph as a proxy, so the nodes don't all have to connect to each other individually.
Biology has many examples of the NxM problem, including thermodynamic coupling. If you ever learned about the tricarboxylic acid cycle, you probably recall a molecule called Adenosine Triphosphate, or ATP. You were likely taught ATP is a 'high energy molecule' that the cell can use to fuel itself. In our graph above, 'money' has a similar function to ATP, acting as an intermediary between reactions that require energy, and reactions that release energy.
Each one of the black lines above actually represents many enzymes, or the proteins that catalyze the reactions occuring. ATP (NADH and others) is created by reactions that release a lot of energy, like the breakdown of glucose (Glycolysis). This energy can then be coupled to reactions that consume energy to do work.
The enzymes that couple ATP Hydrolysis or ATP Synthesis are so common they are given the name ATPases. Some examples include:
- ATP Synthase: This thing is cool. It's got a spinning head and stable tail sitting in the mitochondrial wall. Its head is spun at 130 rotations per second by H+ ions pushing out of the mitochondria. This spinning force pushes ADP + Pi together to form ATP. You think humans invented the pump? Think again :-)
- p97 couples ATP hydrolysis to the movement of tagged (via ubiquitylation) proteins. Essentially P97 is a gatekeeper that only allows certain pre-tagged proteins through a lipid membrane.
- Myosin ATPase couples ATP hydrolysis to muscular movement by 'walking' along an actin filament. The Myosin takes 'steps' about 5-10nm long for every ATP that is hydrolyzed.
- Hexokinase couples ATP hydrolysis to the first step in glycolysis, where glucose is transformed into G6P. Wait, didn't we already couple glycolysis to ATP production? Yup, Hexokinase takes a bit of ATP to start the process, and in turn glycolysis produces even more. The entire TCA cycle yields 2 extra ATP. Gotta have money to make money.
These are just a few of the many enzymes that couple to ATP synthesis or breakdown. Now imagine taking ATP out of the equation. We'd need an enzyme to couple fatty acid oxidation or glycolysis to every action the cell needs to take. That is a big M in our NxM equation.
Line voltage (in the US 120V) is another example of solving the NxM problem. Let's draw our favorite graph again:
Here we're using 3 completely different technologies to create 'line voltage'. Line voltage is a bit hand wavy, but let's assume for now that all electricity in the lines from the generators to your house is 120V (it is not), and call it all line voltage. With line voltage, we can do some useful stuff including:
- Power your shiny new PS5. This involves a Transformer which changes the line voltage down from 120V to ~1.36V for the PS5's AMD processor.
- Boil water in an electric kettle. The line voltage is 'pulled' through a heating element with high resistance, creating a bunch of heat in the process. This heat then boils water for your cup of tea.
- Knead some dough in a stand mixer. The mixer has a big motor in it which probably combines electromagnets and permanent magnets in a creative way to always 'push' the motor around in one direction. The line voltage (after a voltage transform) powers the electromagnets.
This didn't have to be this way. Nuclear and coal power plants already give us precisely what we need to boil water and mix dough. The power plants both work by boiling water before sending the resulting steam to a turbine generator. Why not send that boiling water straight into your kitchen? You certainly could, but we'd need a way to pump the water and keep it hot on the way to the house. We might even need 'booster' stations to reheat it on the way.
Again with dough mixing, nuclear and coal give us exactly what we need: a big spinny thing. But again it's hard to use that energy - imagine in addition to water, sewage, electrical, the city ran a shaft spinning 3000 RPM straight into your basement to power all the things that spin in your house. It could be done, but that is a lot of mass to keep spinning 24/7 and a lot of mechanical transmissions (at least one for each house and each device).
Side note: the alternate reality where spinning rods power everything is called Steampunk.
When should the NxM problem be solved?
When the cost of N-1 edges and a new node is much greater than the cost of rebuilding the system to have N+1 new edges. Running electricity to every home on the planet is hard. Running spinning rods, boiling water, and lines carrying voltage matching every new widget is much much harder. It is no wonder even though nature evolved spinning shafts with gears, it didn't use these to power everything in our bodies. Instead it evolved to solved the NxM problem by using a common high energy molecule to power many biochemical processes.
The NxM problem, or things that look like it, comes up constantly for me at work and in conversation. Now that it has a conceptual label in your brain, you might notice many instances of the NxM problem around you. Have another fun example of the NxM problem? Know other names that are used to refer to this problem? I want to hear about them! Email me at nxm [at] shendrickson.com with your ideas and examples.