JohnVervaeke “Combinatorial explosion” refers to the manner in which a relatively small number of elements can be recombined with each other in sufficiently numerous ways such that it is often impossible to consider each possible combination individually. This is part of why computation is not sufficient for explaining intelligent problem-solving.
For a detailed explication of this concept in context of AI problem solving, see “Relevance Realization and the emerging framework in cognitive science” (Vervaeke, Lillicrap, Richards, 2012), under the heading “Relevance Realization and Problem Solving) The initial coinage of the term “combinatorial explosion” goes back to Keith J. Hollyoak (1995) in chapter 8 of “Problem Solving”.
Newell and Simon’s General Problem Solver model (GPS) posits an initial state, a goal state, a set of operators which an agent can use to transform one state into another, and a set of path constraints which disallow certain types of solutions. These elements generate a problem space or search space consisting of all the possible sequences of states that the agent can take from the initial state to the goal state while obeying path constraints.
The formula for the number of possible sequences in the search space may be expressed by the formula F^D, where F is the number of operators and D is the number of discrete possible states.
The Chess Example: In an average game of chess, 30 moves are possible per turn, and games typically take 60 turns. The corresponding search space for the typical chess therefore consists of 30^60 possibilities. This number is far too large for any conceivable computer to consider algorithmically. For comparison, the estimated number of electrons in the universe has been estimated at 10^79.
Related: Newell and Simon’s General Problem Solver (GPS), ill-defined vs Well-defined problems, algorithmically, heuristics, the finitary predicament, relevance-realization
Mathematically, given n objects from which you can choose r, there are an exponentially increasing number of ways you could arrange those objects, even accounting for repetition and order. This not only makes thinking about them difficult for a human (even the case of the slowest increasing arrangement, nCr, something as ‘simple’ as “how many different kinds of ice cream cones could you make given three scoops and five flavors” is more efficient to calculate rather than writing out individually and then counting by hand), there are problems that are not efficient even for a computer to solve (cryptographic keys are generated by multiplying large prime numbers together, relying on the difficulty of prime factorization, something that may not be solvable at all in polynomial time).
Related: 2017 Maps of Meaning 12： Final： The Divinity of the Individual (6V1eMvGGcXQ) Theology & John Vervaeke: David Bentley Hart, Consciousness, & the Slain Lamb Prototype (Part 2) (youtube.com) Ep. 27 - Awakening from the Meaning Crisis - Problem Formulation (9j5O-tnaFzE)