Combinatorial explosion

In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to justify the intractability of certain problems.[1][2] Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function.

Examples

Latin squares

Main article: Latin square

A Latin square of order n is an n × n array with entries from a set of n elements with the property that each element of the set occurs exactly once in each row and each column of the array. An example of a Latin square of order three is given by,

1	2	3
2	3	1
3	1	2

A common example of a Latin square would be a completed Sudoku puzzle.[3] A Latin square is a combinatorial object (as opposed to an algebraic object) since only the arrangement of entries matters and not what the entries actually are. The number of Latin squares as a function of the order (independent of the set from which the entries are drawn) (sequence A002860 in the OEIS) provides an example of combinatorial explosion as illustrated by the following table.

n	The number of Latin squares of order n
1	1
2	2
3	12
4	576
5	161,280
6	812,851,200
7	61,479,419,904,000
8	108,776,032,459,082,956,800
9	5,524,751,496,156,892,842,531,225,600
10	9,982,437,658,213,039,871,725,064,756,920,320,000
11	776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000

Sudoku

Main article: Mathematics of Sudoku

A combinatorial explosion can also occur in some puzzles played on a grid, such as Sudoku.[2] A Sudoku is a type of Latin square with the additional property that each element occurs exactly once in sub-sections of size √n×√n (called boxes). Combinatorial explosion occurs as n increases, creating limits to the properties of Sudokus that can be constructed, analyzed, and solved, as illustrated in the following table.

n	The number of Sudoku grids of order n (boxes are size√n×√n)	The number of Latin squares of order n (for comparison)
1	1	1
4	288 [4][5]	576
9	6,670,903,752,021,072,936,960 [4][6]	5,524,751,496,156,892,842,531,225,600
16	5.96×10^98 (estimated) [7]	—
25	4.36×10^308 (estimated) [8]	—
(n = 9 is the commonly played 9×9 Sudoku. The puzzle does not include grids where √n is irrational.)

Games

One example in a game where combinatorial complexity leads to a solvability limit is in solving chess (a game with 64 squares and 32 pieces). Chess is not a solved game. In 2005 all chess game endings with six pieces or fewer were solved, showing the result of each position if played perfectly. It took ten more years to complete the tablebase with one more chess piece added, thus completing a 7-piece tablebase. Adding one more piece to a chess ending (thus making an 8-piece tablebase) is considered intractable due to the added combinatorial complexity.[9][10]

Furthermore, the prospect of solving larger chess-like games becomes more difficult as the board-size is increased, such as in large chess variants, and infinite chess.[11]

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.

A class hierarchy in an object-oriented language 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.

An example is a taxonomy 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 multiply 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:

${\displaystyle 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.[12]

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. (This growth is often casually described as "exponential" but is actually 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 ${\displaystyle 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).[13]

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.

See also

• Birthday problem
• Metcalfe's law
• Curse of dimensionality
• Intractability (complexity)
• Second half of the chessboard

References

1. Krippendorff, Klaus. "Combinatorial Explosion". Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB. Retrieved 29 November 2010.
2. http://intelligence.worldofcomputing/combinatorial-explosion Combinatorial Explosion.
3. All completed puzzles are Latin squares, but not all Latin squares can be completed puzzles since there is additional structure in a Sudoku puzzle.
4. Sloane, N. J. A. (ed.). "Sequence A107739 (Number of (completed) sudokus (or Sudokus) of size n^2 X n^2)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. Retrieved 14 April 2017.
5. "Sudoku maths - can mortals work it out for the 2x2 square ? : General". Forum.enjoysudoku.com. Retrieved 2013-10-20.
6. "Sudoku enumeration problems". Afjarvis.staff.shef.ac.uk. Retrieved 20 October 2013.
7. "Su-Doku's maths : General - Page 36". Forum.enjoysudoku.com. Retrieved 2013-10-20.
8. "RxC Sudoku band counting algorithm : General". Forum.enjoysudoku.com. Retrieved 2013-10-20.
9. http://chessok.com/Lomonosov Endgame Tablebases Lomonosov Endgame Tablebases
10. http://chess.stackexchange.com/7-piece-endgame-tablebase (chess) 7-piece-endgame-tablebase (chess)
11. Aviezri Fraenkel; D. Lichtenstein (1981), "Computing a perfect strategy for n×n chess requires time exponential in n", J. Combin. Theory Ser. A, 31 (2): 199–214, doi:10.1016/0097-3165(81)90016-9
12. http://www.physicsoftheuniverse.com/numbers.html
13. Benson, Tim. (2010). Principles of health interoperability HL7 and SNOMED. New York: Springer. p. 23. ISBN 9781848828032. OCLC 663097524.