Add One More Item and the Problem Becomes a Million Times Harder

Arranging five items in order gives one hundred and twenty possibilities. Ten items give more than three million. Fifteen give over a thousand million million. Twenty give a number with nineteen digits. Each additional item multiplies the total by the new count, so growth accelerates rather than merely continuing, and the numbers pass beyond anything physical very quickly. A problem requiring every arrangement to be examined is therefore not merely slow at moderate sizes, it is permanently out of reach.

The pattern turns up wherever combinations must be considered:

• •Planning a route visiting many places in the best order
• •Scheduling staff, rooms or machines against many constraints
• •Testing every combination of settings in a complex system
• •Searching game positions several moves ahead
• •Checking every subset of a collection for some property
• •Any situation where choices multiply rather than adding

The instinctive response is to use a faster machine, and the arithmetic makes that hopeless. A machine a thousand times faster handles a problem only a few items larger before hitting the same wall, because the growth multiplies while the improvement adds. Doubling processor speed every couple of years for decades moves the boundary by a handful of items in total. That is the practical meaning of the distinction computer science draws between problems whose difficulty grows manageably with size and problems whose difficulty grows this way, and it is why the distinction matters rather than being a technicality.

Placing this among the other growth rates makes clear why it is the one that matters. A problem whose difficulty doubles with each added item is already severe, and one whose difficulty multiplies by the new count is worse again, since the multiplier itself keeps rising. Below both sit growth rates that square or cube with size, which are demanding at large sizes and entirely tractable at small ones, and below those sit rates that grow barely at all. The dividing line drawn in computer science falls between the polynomial rates and the rest, and it is drawn there because that is where more hardware stops helping.

Practical work abandons the search for the guaranteed best answer and uses methods that produce good answers quickly. Pruning discards whole branches once they are known to be worse than something already found, which can eliminate most of the space without examining it. Heuristics use rules of thumb to choose promising directions. Approximation algorithms guarantee an answer within a stated distance of the best. Randomised methods sample the space rather than exhausting it. Constraint solvers exploit structure in the problem. Real route planning and scheduling use combinations of these and never examine every possibility.

Each item added multiplies the number of arrangements rather than adding to it, so twenty items already give a nineteen digit total and exhaustive examination becomes impossible at trivial sizes. A machine a thousand times faster buys only a few more items, which is why the growth rate matters more than the hardware. Practical work prunes, approximates and samples instead.