Combinatorial explosion

From Wikipedia, the free encyclopedia

In mathematics a combinatorial explosion describes the effect of functions that grow very rapidly as a result of combinatorial considerations.^[1]

Examples of such functions include the factorial function and related functions. Pathological examples of combinatorial explosion include functions such as the Ackermann function.

Examples

Computing

Combinatorial explosion can occur in computing environments in a way analogous to communications and multi-dimensional space. Imagine a simple system with only one variable, a boolean called A. The system has two possible states, A = true or A = false. Adding another boolean variable B will give the system four possible states, A = true and B = true, A = true and B = false, A = false and B = true, A = false and B = false. A system with n booleans has 2ⁿ possible states, while a system of n variables each with Z allowed values (rather than just the 2 (true and false) of booleans) will have Zⁿ possible states.

The possible states can be thought of as the leaf nodes of a tree of height n, where each node has Z children. This rapid increase of leaf nodes can be useful in areas like searching, since many results can be accessed without having to descend very far. It can also be a hindrance when manipulating such structures.

Consider a class hierarchy in an object-oriented language. The hierarchy can be thought of as a tree, with different types of object inheriting from their parents. If different classes need to be combined, such as in a comparison (like A < B) then the number of possible combinations which may occur explodes. If each type of comparison needs to be programmed then this soon becomes intractable for even small numbers of classes. Multiple inheritance can solve this, by allowing subclasses to have multiple parents, and thus a few parent classes can be considered rather than every child, without disrupting any existing hierarchy.

For example, imagine a hierarchy where different vegetables inherit from their ancestor species. Attempting to compare the tastiness of each vegetable with the others becomes intractable since the hierarchy only contains information about genetics and makes no mention of tastiness. However, instead of having to write comparisons for carrot/carrot, carrot/potato, carrot/sprout, potato/potato, potato/sprout, sprout/sprout, they can all inherit from a separate class of tasty whilst keeping their current ancestor-based hierarchy, then all of the above can be implemented with only a tasty/tasty comparison.

Arithmetics

Suppose we take the factorial for n:

$n!=(n)(n-1)...(2)(1)$

Then 1! = 1, 2! = 2, 3! = 6, and 4! = 24. However, we quickly get to extremely large numbers, even for relatively small n. For example, 100! = 9.33262154 × 10¹⁵⁷, a number so large that it cannot be displayed on most calculators, and vastly larger than the estimated number of fundamental particles in the Universe.^[2]

For other uses, see Combinatorial explosion.

Using separate lines of communication, four organizations require six channels

Using an intermediary, only one channel per organization is required

Communication

In administration and computing, a combinatorial explosion is the rapidly accelerating increase in communication lines 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}}={n \choose 2}$ communication lines for n organizations, which is just the number of 2-combinations of n elements, see also binomial coefficient .

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.

References

↑ Krippendorff, Klaus. "Combinatorial Explosion". Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB. Retrieved 29 November 2010.
↑ http://www.physicsoftheuniverse.com/numbers.html

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.