Complexity of Search
Branching factors, depth and the price of completeness.
Every uninformed algorithm costs about in the worst case. Is that a weakness of the algorithms, or a law? This lesson proves it is a law for blind search, measures the true of real puzzles, and places search on the map of complexity theory, where a few landmark results say how much of the exponential can ever be removed.
What you’ll learn
- Define asymptotic and effective branching factors, and derive the asymptotic branching factor of the 8-puzzle.
- Prove that every complete blind search must generate about nodes in the worst case, and explain in what sense iterative deepening is optimal.
- Show that uniform-cost search's bound is tight, and what zero and negative costs do.
- Place search problems in complexity theory: explicit versus implicit graphs, Savitch's theorem, NP-hard puzzle optimization and PSPACE-complete planning.
Measuring a search space
Real problems are not uniform trees. In the 8-puzzle the blank has 2 moves in a corner, 3 on an edge and 4 in the center, and search programs never undo the previous move (parent pruning), which removes one option from each. The resulting is the growth rate of a small linear recurrence over where the blank is.
With parent pruning, the 8-puzzle's blank has 1, 2 or 3 new moves depending on its position. Predict the asymptotic branching factor before you reveal the derivation.
Show the answer
1.73
. The center, with 3 new moves, is visited less often than the corners, which have only 1, so the average is well below 2. Depth-20 search therefore generates on the order of nodes at depth 20, not .
Count depth- nodes by the blank's position and where it came from: (corner), (edge, entered from a corner), (edge, entered from the center) and (center). With parent pruning, one more move maps the counts to
The growth rate is the largest eigenvalue of this linear map. An eigenvector has , and ; substitute into the first equation:
So . The same method gives about for the 15-puzzle (Edelkamp & Korf, 1998) and about for Rubik's cube with 18 face turns, after pruning consecutive turns of the same face and fixing the order of turns of opposite faces (Korf, 1997).
The price of completeness: a lower bound
The adversary answers "not a goal" to every test of a depth- node until only one depth- node is left untested, and places the goal there. Every answer is consistent with a valid instance, and the algorithm must generate the goal in order to return it, so it generates all depth- nodes:
A node can be generated only after its parent is expanded, so all nodes above depth are generated too. Breadth-first search with the early goal test meets this bound exactly:
Randomized algorithms. By Yao's principle, it suffices to bound the best deterministic algorithm against a uniformly random goal. Whatever order it generates the depth- nodes in, the goal's position in that order is uniform on , so randomization saves at most a factor of 2:
Space has its own trade-off. BFS stores nodes; depth-first methods store , or when they generate one successor at a time. Korf (1985) showed that iterative deepening is asymptotically optimal among brute-force tree searches in time, space and solution length: it matches the lower bound up to the factor , its memory is linear in the depth, and it returns a shallowest solution.
Costs, not steps
For uniform-cost search the depth is the wrong yardstick. The Hidden Layer proved the bound : every node with may be expanded, and such nodes can lie up to deep. Is the bound tight, or an artifact of the proof?
Let the root have one action of cost 1 leading to the goal, and let the root and every other node also have actions of cost leading to non-goal nodes. Then
UCS pops nodes in order of . The goal sits on the frontier with after the first expansion, but it waits behind every cheap node with , that is, every path of fewer than cheap steps:
BFS with the early goal test generates nodes on the same tree. Up to the base of the exponential, UCS's bound is attained: the price of guaranteed optimality is set by the cost ratio , not by the depth.
The assumptions matter. With , a cycle of zero-cost actions yields infinitely many nodes with , and tree-like UCS need not terminate; graph search fixes this in finite spaces. With negative costs the ordering argument collapses: Dijkstra's invariant fails, and on explicit graphs one needs the Bellman–Ford algorithm's time, which also detects negative cycles, in whose presence no optimal path exists.
Search in the landscape of complexity theory
Complexity theory measures cost against the size of the input, and for search the input is usually not the graph. On an explicit graph with vertices and edges, BFS runs in time and Dijkstra's algorithm in with Fibonacci heaps (Fredman & Tarjan, 1987): polynomial. AI's state spaces are implicit, generated from a compact description such as state variables or the rules of a puzzle, and can have states. Polynomial in is exponential in .
| Problem | Complexity | Reference |
|---|---|---|
| Shortest paths in an explicit graph, nonnegative costs | Dijkstra (1959); Fredman & Tarjan (1987) | |
| Reachability in an undirected explicit graph | deterministic logspace | Reingold (2008) |
| Reachability among implicit states | space | Savitch (1970) |
| Plan existence in propositional STRIPS | PSPACE-complete | Bylander (1994) |
| Solvability of the 15-puzzle and its versions | polynomial: a parity test | Johnson & Story (1879) |
| Shortest solution of the -puzzle | NP-hard | Ratner & Warmuth (1990) |
| Optimal solution of the Rubik's cube | NP-complete | Demaine, Eisenstat & Rudoy (2018) |
Let ask whether can be reached from in at most steps. Split such a path at its midpoint and try every candidate midpoint in turn, reusing the same space:
A reachable target is always reachable in fewer than steps, so the recursion is levels deep, and each level stores only its , , and a counter, bits:
The price is time. Each level makes up to recursive calls, so the running time is , superpolynomial. Middle-first search is one extreme of the time–space trade-off and BFS (linear time and space) the other; on trees, iterative deepening sits in between.
Savitch's middle-first search decides reachability in an -state graph in space. Why don't practical search programs use it instead of BFS?
- It works only on undirected graphs
- Its running time is , superpolynomial in the number of states
- Its recursion stack needs space after all
- It cannot handle implicit graphs
Show the answer
B. Its running time is , superpolynomial in the number of states
Middle-first search recomputes the same subproblems over and over: up to calls per level, over levels. BFS spends memory to touch each state once. Practical memory-bounded methods such as iterative deepening and IDA* accept a constant-factor time overhead on trees instead.
Key takeaways
- Real branching factors are smaller than they look: the 8-puzzle's asymptotic branching factor is and the 15-puzzle's about , while the effective branching factor measures one particular search.
- Blind search cannot beat the tree: an adversary forces every deterministic algorithm to generate all nodes down to depth , randomization saves at most a factor 2, and iterative deepening matches this within in linear space.
- UCS's is essentially tight: cheap, useless actions can make it exponentially slower than BFS. Zero-cost cycles break completeness and negative costs break correctness.
- Search is polynomial in the number of states but exponential in the description: optimal sliding-tile solving is NP-hard and STRIPS planning is PSPACE-complete, while Savitch's theorem decides reachability in space at superpolynomial cost in time.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why does depth- search in the 15-puzzle cost roughly rather than ?
- Half of all tile arrangements are unreachable
- A good heuristic prunes about half of the moves
- The blank often has fewer than 4 moves, and search never undoes the previous move
- The puzzle has only 16 squares, so the tree is finite
Show the answer
C. The blank often has fewer than 4 moves, and search never undoes the previous move
Corner and edge positions of the blank offer 2 or 3 moves, and parent pruning removes one more. The asymptotic branching factor of the pruned brute-force tree is about ; no heuristic is involved.
What does the adversary argument for blind search prove?
- Breadth-first search is the only optimal blind search
- On a uniform tree, every deterministic blind search can be forced to generate every node of depth at most
- No algorithm, even one with a heuristic, can beat
- Randomized search needs only about goal tests
Show the answer
B. On a uniform tree, every deterministic blind search can be forced to generate every node of depth at most
The adversary keeps answering "not a goal" until one depth- node is left. All depth- nodes must be generated, and their ancestors too: at least nodes. Randomization only halves the expected work.
In a tree, the goal is one step from the root at cost 1, while every node also has actions of cost that never lead to a goal. How does uniform-cost search behave?
- It finds the goal after one expansion, like breadth-first search
- It never terminates
- It returns a suboptimal path
- It expands every cheap path of cost below 1, about nodes, before popping the goal
Show the answer
D. It expands every cheap path of cost below 1, about nodes, before popping the goal
The goal sits on the frontier with from the start, but UCS must first pop every node with : all paths of up to 99 cheap steps. This matches the bound up to the base, so the bound is essentially tight. BFS with its early goal test would generate only nodes.
Dijkstra's algorithm runs in polynomial time, yet finding a shortest solution of the sliding-tile puzzle is NP-hard. Why is there no contradiction?
- Dijkstra's algorithm is polynomial in the number of states, which is exponential in
- Dijkstra's algorithm fails on puzzles because moves are reversible
- The puzzle has negative step costs
- NP-hardness applies only to randomized algorithms
Show the answer
A. Dijkstra's algorithm is polynomial in the number of states, which is exponential in
The puzzle has reachable states, described by only bits. Running time polynomial in the size of an explicit graph is exponential in the size of an implicit description.
Further reading
- R. E. Korf, "Depth-first iterative-deepening: An optimal admissible tree search," Artificial Intelligence 27(1) (1985), 97–109.
- W. J. Savitch, "Relationships between nondeterministic and deterministic tape complexities," Journal of Computer and System Sciences 4(2) (1970), 177–192.
- D. Ratner & M. Warmuth, "The -puzzle and related relocation problems," Journal of Symbolic Computation 10(2) (1990), 111–137.
- T. Bylander, "The computational complexity of propositional STRIPS planning," Artificial Intelligence 69 (1994), 165–204.
- S. Arora & B. Barak, Computational Complexity: A Modern Approach (Cambridge University Press, 2009), chapter 4.