The NxM problem

Posted on

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.

flowchart LR; sheep <--> wheat; sheep <--> wood; sheep <--> clay; sheep <--> ore; wheat <--> wood; wheat <--> clay; wheat <--> ore; wood <--> clay; wood <--> ore; clay <--> ore;

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.

flowchart TD; sheep1["sheep"] <--> money(money); wheat1["wheat"] <--> money; wood1["wood"] <--> money; clay1["clay"] <--> money; ore1["ore"] <--> money; style money fill:#6b7

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.

Thermodynamic Coupling

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.

flowchart LR; glycolysis["Glycolysis"] -- indirectly fuels ATP Synthase --> atp(ATP); pyruvate["Pyruvate Oxidation"] -- indirectly fuels ATP Synthase --> atp; betaox["Fatty Acid Oxidation"] -- indirectly fuels ATP Synthase --> atp; atp --> protein["Protein Synthesis"] atp -- p97 --> comms["Protein Recycling"] atp -- Myosin ATPase --> move["Muscle Contraction"] atp -- Hexokinase --> g6p["First step in glycolysis"] style atp fill:#6b7

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:

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

Line voltage (in the US 120V) is another example of solving the NxM problem. Let's draw our favorite graph again:

flowchart LR; coal["Coal"] -- boils water to spin generator --> line("line voltage*"); nuclear["Nuclear Fission"] -- boils water to spin generator --> line; solar["Solar Panels"] -- photons excite charge carriers --> line; line -- Transformed to 1.36V --> ps5["Powers PS5"]; line -- Heats heating element --> kettle["Boils water"]; line -- Powers some electromagnets --> mixer["Kneads some dough"]; style line fill:#6b7

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:

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.

Wrapping Up

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] with your ideas and examples.

Happy Transforming!