Definition
Combinatorial Explosion is the phenomenon where the number of possible combinations or states in a search space grows exponentially with the size of the problem. In artificial intelligence, this represents the primary bottleneck for exhaustive search methods, where even slightly more complex tasks become computationally infeasible.
Why It Matters
It defines the fundamental limits of search-based problem solving and explains why domain knowledge and heuristics are necessary for intelligence.
Core Concepts
- Exponential Growth of States: For a problem with steps and choices at each step, the total number of states is .
- How to read: “The value m to the n.”
- Meaning / when to use: Total states for steps with choices each—each independent choice multiplies the search space; why exhaustive search fails at modest depth.
- Exhaustive Search Failure: Early AI systems (like Logic Theorist) could solve simple proofs but failed on complex ones because they couldn’t comb through the + possible sequences required for longer proofs.
- The “Look, Ma, no hands!” Era: A term by John McCarthy describing the early period of AI where researchers showed proofs-of-concept in “microworlds” (pared-down versions of reality) to avoid the combinatorial explosion.
- Heuristic Search as a Solution: To overcome the explosion, AI must exploit structure in the domain using “rules of thumb” (heuristics) to prune the search tree and focus on the most promising paths.