Combinatorial explosion (communication)

From Wikipedia, the free encyclopedia

For other uses, see Combinatorial explosion.

Using separate lines of communication, four organizations require six channels

In administration and computing, a combinatorial explosion is the rapidly accelerating increase in lines of communication as organizations are added in a process. (Casually described as "exponential" it is actually strictly only polynomial)

If two organizations need to communicate about a particular topic, it may be easiest to communicate directly in an ad hoc manner—only one channel of communication is required. However, if a third organization is added, three separate channels are required. Adding a fourth organization requires six channels; five, ten; six, fifteen; etc.

In general, going on like that, it will take $l=\frac{n(n-1)}{2}$ communication lines for n organizations.

Using an intermediary, only one channel per organization is required

The alternative approach is to realize when this communication will not be a one-off requirement, and produce a generic or intermediate way of passing information. The drawback is that this requires more work for the first pair, since each must convert its internal approach to the common one, rather than the superficially easier approach of just understanding the other.

An element of cryptologic/cryptographic work involves producing combinatorial explosions in order to multiply the work of solving the cipher beyond the time and resources available.