The exponential growth rate experienced in many search problems. For example, in the game of chess the number of choices at each level increases by the branching factor, which may typically multiply the options by 20 or more at each move. Although in theory it should be possible to analyse the game of chess from start to finish, the number of states to be examined is so enormous that it is completely impractical, not only at present but for any conceivable computer in the future.

One of the main thrusts of artificial intelligence work has been to find ways, such as heuristic search, to circumvent the combinatorial explosion.