combinatorial explosion
In plain wordsThe way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers.
The rapid, typically exponential or factorial, growth in the number of states, paths or candidate solutions as a problem's size increases, which defeats exhaustive search. A game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws. with branching factor b searched to depth d has b^d leaves; the number of possible tours through n cities grows as n!; a planning problem described by n true-or-false facts has 2^n states. Combinatorial explosion explains why early AI successes in toy domains failed to scale, and why AI relies on heuristicsheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., pruning, abstraction, problem decomposition, symmetry breaking and learned guidance. In formal verificationformal verification, n.: Using mathematics, not just testing, to prove that a computer system always behaves as specified — for example, that a chip never adds wrongly or that a program can never crash in a particular way. the same phenomenon is called state explosion.
Adding a tenth delivery van caused a combinatorial explosion in the routing problem.
Origin
Brought to wide attention by James Lighthill's 1973 report to the UK Science Research Council, which argued that AI methods could not overcome combinatorial explosion outside toy problems and contributed to cuts in British AI funding. The phrase's earliest use has not been established.
Usage note
Exponential growth does not always mean practical hopelessness: SAT solversBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep. and learned search policies routinely tame enormous spaces by exploiting their structure.
Related
- NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all.
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
- game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws.
- Lighthill reportLighthill report, prop. n.: A 1973 review written for a British government research council that judged AI research to have fallen far short of its promises. It led to deep cuts in AI funding in the United Kingdom.
- AI winterAI winter, n.: A slump in which disappointment over AI's unmet promises leads governments and companies to pull back money and attention. Historians count two big ones: one in the 1970s and one starting in the late 1980s.
Sources
- Lighthill, J. (1973). Artificial Intelligence: A General Survey. In Artificial Intelligence: A Paper Symposium. Science Research Council, London.
Mentioned in
Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws., General Problem SolverGeneral Problem Solver, prop. n.: A 1950s program meant to solve any well-defined puzzle by repeatedly comparing where it was with where it wanted to be and choosing steps that closed the gap., heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all., state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal., traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added.