PostHeaderIcon Combinatorial Explosion

What is Combinatorial Explosion?


The problem with all brute-force search algorithms is that their time complexities grow exponentially with problem size. This problem is called combinatorial explosion.

The combinatorial explosion results in limited size of problems that can be solved with with brute-force search techniques. For example while eight-puzzle with 105 states is easily solved by brute-force search, the fifteen-puzzle contains over 1013 states, and hence cannot be solved with brute-force techniques on current machines. Even faster machines cannot have significant impact on this problem since the 5 * 5 twenty-four puzzle contains almost 1025 states.