Combinatorial explosion

For other uses, see Combinatorial explosion (communication).

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.

Example in 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.

Example in arithmetic

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.

See also

• Intractability (complexity)
• Curse of dimensionality
• Second half of the chessboard

References

1. ^ Krippendorff, Klaus. "Combinatorial Explosion". Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB. http://pespmc1.vub.ac.be/ASC/Combin_explo.html. Retrieved 29 November 2010.