Tutorial by Edward Tsang

Combinatorial Explosion

Combinatorial explosion is a fundamental problem in computing. It is the problem that the number of combinations that one has to examine grows exponentially, so fast that even the fastest computers will require an intolerable amount of time to examine them.

The combinatorial explosion problem limits the ability of computers to solve large problems. This is because in most realistic problems of interest to us, the number of combinations is typically very large.

Suppose you have n decisions to make and for each decision, you have 10 possible options. Then you will have all together 10 to the power n combinations of solutions. The number of combinations grows exponentially as n increases.

In chess, one could examine every possible move and their subsequent moves. However, if we assume that there are 20 choices per move, then looking ahead 15 moves will involve examination of 20 to the power 15, or 3.3x10^19, sequences. If our computer manages to examine 1,000,000,000 sequences per second (be sure that your desktop computer won't have that speed), a brute force search would have to take over 90 million hours ( over 10,000 years) to make one move, which is obviously unacceptable. To improve the speed of play, one needs either much faster computers or clever algorithms which allows one to be highly selective in what sequences to examine. The combinatorial explosion problem prevented computers from competing with human world champions until recently.