Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Complexity of Search

Branching factors, depth and the price of completeness.

Every uninformed algorithm costs about bdb^d 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 bb 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 bdb^d nodes in the worst case, and explain in what sense iterative deepening is optimal.
  • Show that uniform-cost search's O(b1+⌊C∗/ε⌋)\order{b^{1+\lfloor C^*/\varepsilon\rfloor}} 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 b∞b_\infty is the growth rate of a small linear recurrence over where the blank is.

Predict before you look

With parent pruning, the 8-puzzle's blank has 1, 2 or 3 new moves depending on its position. Predict the asymptotic branching factor b∞b_\infty before you reveal the derivation.

Show the answer

1.73

b∞=3≈1.732b_\infty=\sqrt3\approx1.732. 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 1.7320≈6×1041.73^{20}\approx6\times10^4 nodes at depth 20, not 420≈10124^{20}\approx10^{12}.

DerivationThe 8-puzzle's asymptotic branching factor
  1. c′=e1+2e2,e1′=c,e2′=3m,m′=e1c'=e_1+2e_2,\qquad e_1'=c,\qquad e_2'=3m,\qquad m'=e_1

    Count depth-kk nodes by the blank's position and where it came from: cc (corner), e1e_1 (edge, entered from a corner), e2e_2 (edge, entered from the center) and mm (center). With parent pruning, one more move maps the counts to

  2. λc=cλ+6cλ3⟹λ4−λ2−6=(λ2−3)(λ2+2)=0\lambda c=\frac c\lambda+\frac{6c}{\lambda^3}\quad\Longrightarrow\quad\lambda^4-\lambda^2-6=(\lambda^2-3)(\lambda^2+2)=0

    The growth rate is the largest eigenvalue λ\lambda of this linear map. An eigenvector has e1=c/λe_1=c/\lambda, m=c/λ2m=c/\lambda^2 and e2=3c/λ3e_2=3c/\lambda^3; substitute into the first equation:

  3. b∞(8-puzzle)=3≈1.732,b∞(15-puzzle)≈2.130,b∞(cube)≈13.35b_\infty(\text{8-puzzle})=\sqrt3\approx1.732,\qquad b_\infty(\text{15-puzzle})\approx2.130,\qquad b_\infty(\text{cube})\approx13.35

    So b∞=3b_\infty=\sqrt3. The same method gives about 2.1302.130 for the 15-puzzle (Edelkamp & Korf, 1998) and about 13.3513.35 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

DerivationProof: an adversary hides the goal
  1. #{depth-d nodes generated}=bd\#\{\text{depth-}d\text{ nodes generated}\}=b^d

    The adversary answers "not a goal" to every test of a depth-dd node until only one depth-dd 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 bdb^d depth-dd nodes:

  2. nodes generated ≥ ∑k=0dbk=bd+1−1b−1\text{nodes generated}\ \ge\ \sum_{k=0}^{d}b^k=\frac{b^{d+1}-1}{b-1}

    A node can be generated only after its parent is expanded, so all nodes above depth dd are generated too. Breadth-first search with the early goal test meets this bound exactly:

  3. E[depth-d nodes generated] ≥ 1bd∑i=1bdi=bd+12\E[\text{depth-}d\text{ nodes generated}]\ \ge\ \frac1{b^d}\sum_{i=1}^{b^d}i=\frac{b^d+1}2

    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-dd nodes in, the goal's position in that order is uniform on {1,…,bd}\{1,\dots,b^d\}, so randomization saves at most a factor of 2:

Space has its own trade-off. BFS stores Θ(bd)\Theta(b^d) nodes; depth-first methods store O(bd)\order{bd}, or O(d)\order{d} 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 b/(b−1)b/(b-1), its memory is linear in the depth, and it returns a shallowest solution.

Costs, not steps

For uniform-cost search the depth dd is the wrong yardstick. The Hidden Layer proved the bound O(b1+⌊C∗/ε⌋)\order{b^{1+\lfloor C^*/\varepsilon\rfloor}}: every node with g<C∗g<C^* may be expanded, and such nodes can lie up to C∗/εC^*/\varepsilon deep. Is the bound tight, or an artifact of the proof?

DerivationA family where UCS is exponentially slower than BFS
  1. C∗=1,d=1,C∗/ε=KC^*=1,\qquad d=1,\qquad C^*/\varepsilon=K

    Let the root have one action of cost 1 leading to the goal, and let the root and every other node also have b−1b-1 actions of cost ε=1/K\varepsilon=1/K leading to non-goal nodes. Then

  2. #{nodes expanded before the goal} ≥ ∑j=0K−1(b−1)j ≥ (b−1)C∗/ε−1\#\{\text{nodes expanded before the goal}\}\ \ge\ \sum_{j=0}^{K-1}(b-1)^j\ \ge\ (b-1)^{C^*/\varepsilon-1}

    UCS pops nodes in order of gg. The goal sits on the frontier with g=1g=1 after the first expansion, but it waits behind every cheap node with g<1g<1, that is, every path of fewer than KK cheap steps:

  3. NUCS=Ω((b−1)C∗/ε−1)vs.NBFS=b+1N_{\mathrm{UCS}}=\Omega\big((b-1)^{C^*/\varepsilon-1}\big)\qquad\text{vs.}\qquad N_{\mathrm{BFS}}=b+1

    BFS with the early goal test generates b+1b+1 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 C∗/εC^*/\varepsilon, not by the depth.

The assumptions matter. With ε=0\varepsilon=0, a cycle of zero-cost actions yields infinitely many nodes with g<C∗g<C^*, 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 O(VE)\order{VE} 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 VV vertices and EE edges, BFS runs in O(V+E)\order{V+E} time and Dijkstra's algorithm in O(E+Vlog⁡V)\order{E+V\log V} with Fibonacci heaps (Fredman & Tarjan, 1987): polynomial. AI's state spaces are implicit, generated from a compact description such as nn state variables or the rules of a puzzle, and can have 2n2^n states. Polynomial in VV is exponential in nn.

ProblemComplexityReference
Shortest paths in an explicit graph, nonnegative costsO(E+Vlog⁡V)\order{E+V\log V}Dijkstra (1959); Fredman & Tarjan (1987)
Reachability in an undirected explicit graphdeterministic logspaceReingold (2008)
Reachability among 2n2^n implicit statesO(n2)\order{n^2} spaceSavitch (1970)
Plan existence in propositional STRIPSPSPACE-completeBylander (1994)
Solvability of the 15-puzzle and its n×nn\times n versionspolynomial: a parity testJohnson & Story (1879)
Shortest solution of the (n2−1)(n^2-1)-puzzleNP-hardRatner & Warmuth (1990)
Optimal solution of the n×n×nn\times n\times n Rubik's cubeNP-completeDemaine, Eisenstat & Rudoy (2018)
Deciding whether a puzzle can be solved is often easy; finding an optimal solution is where hardness appears.
DerivationMiddle-first search
  1. Reach(u,v,k)=⋁w(Reach(u,w,k−1)∧Reach(w,v,k−1)),Reach(u,v,0)=[ u=v or u→v ]\mathrm{Reach}(u,v,k)=\bigvee_{w}\Big(\mathrm{Reach}(u,w,k-1)\wedge\mathrm{Reach}(w,v,k-1)\Big),\qquad\mathrm{Reach}(u,v,0)=[\,u=v\ \text{or}\ u\to v\,]

    Let Reach(u,v,k)\mathrm{Reach}(u,v,k) ask whether vv can be reached from uu in at most 2k2^k steps. Split such a path at its midpoint ww and try every candidate midpoint in turn, reusing the same space:

  2. space=O(log⁡N)⋅O(log⁡N)=O(log⁡2N)\text{space}=\order{\log N}\cdot\order{\log N}=\order{\log^2N}

    A reachable target is always reachable in fewer than NN steps, so the recursion is ⌈log⁡2N⌉\lceil\log_2N\rceil levels deep, and each level stores only its uu, vv, ww and a counter, O(log⁡N)\order{\log N} bits:

  3. T(k)≤2N⋅T(k−1)⟹T=(2N)O(log⁡N)T(k)\le2N\cdot T(k-1)\quad\Longrightarrow\quad T=(2N)^{\order{\log N}}

    The price is time. Each level makes up to 2N2N recursive calls, so the running time is NO(log⁡N)N^{\order{\log N}}, 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.

Check your understanding

Savitch's middle-first search decides reachability in an NN-state graph in O(log⁡2N)\order{\log^2N} space. Why don't practical search programs use it instead of BFS?

  1. It works only on undirected graphs
  2. Its running time is NO(log⁡N)N^{\order{\log N}}, superpolynomial in the number of states
  3. Its recursion stack needs O(N)\order{N} space after all
  4. It cannot handle implicit graphs
Show the answer

B. Its running time is NO(log⁡N)N^{\order{\log N}}, superpolynomial in the number of states

Middle-first search recomputes the same subproblems over and over: up to 2N2N calls per level, over log⁡2N\log_2N levels. BFS spends O(N)\order{N} 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 3\sqrt3 and the 15-puzzle's about 2.132.13, while the effective branching factor measures one particular search.
  • Blind search cannot beat the tree: an adversary forces every deterministic algorithm to generate all (bd+1−1)/(b−1)(b^{d+1}-1)/(b-1) nodes down to depth dd, randomization saves at most a factor 2, and iterative deepening matches this within b/(b−1)b/(b-1) in linear space.
  • UCS's O(b1+⌊C∗/ε⌋)\order{b^{1+\lfloor C^*/\varepsilon\rfloor}} 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 O(log⁡2N)\order{\log^2N} 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.

Question 1

Why does depth-dd search in the 15-puzzle cost roughly 2.13d2.13^d rather than 4d4^d?

  1. Half of all tile arrangements are unreachable
  2. A good heuristic prunes about half of the moves
  3. The blank often has fewer than 4 moves, and search never undoes the previous move
  4. 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 2.132.13; no heuristic is involved.

Question 2

What does the adversary argument for blind search prove?

  1. Breadth-first search is the only optimal blind search
  2. On a uniform tree, every deterministic blind search can be forced to generate every node of depth at most dd
  3. No algorithm, even one with a heuristic, can beat bdb^d
  4. Randomized search needs only about bd\sqrt{b^d} 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 dd

The adversary keeps answering "not a goal" until one depth-dd node is left. All bdb^d depth-dd nodes must be generated, and their ancestors too: at least (bd+1−1)/(b−1)(b^{d+1}-1)/(b-1) nodes. Randomization only halves the expected work.

Question 3

In a tree, the goal is one step from the root at cost 1, while every node also has b−1b-1 actions of cost ε=0.01\varepsilon=0.01 that never lead to a goal. How does uniform-cost search behave?

  1. It finds the goal after one expansion, like breadth-first search
  2. It never terminates
  3. It returns a suboptimal path
  4. It expands every cheap path of cost below 1, about (b−1)99(b-1)^{99} nodes, before popping the goal
Show the answer

D. It expands every cheap path of cost below 1, about (b−1)99(b-1)^{99} nodes, before popping the goal

The goal sits on the frontier with g=1g=1 from the start, but UCS must first pop every node with g<1g<1: all paths of up to 99 cheap steps. This matches the b1+⌊C∗/ε⌋b^{1+\lfloor C^*/\varepsilon\rfloor} bound up to the base, so the bound is essentially tight. BFS with its early goal test would generate only bb nodes.

Question 4

Dijkstra's algorithm runs in polynomial time, yet finding a shortest solution of the n×nn\times n sliding-tile puzzle is NP-hard. Why is there no contradiction?

  1. Dijkstra's algorithm is polynomial in the number of states, which is exponential in nn
  2. Dijkstra's algorithm fails on puzzles because moves are reversible
  3. The puzzle has negative step costs
  4. 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 nn

The puzzle has (n2)!/2(n^2)!/2 reachable states, described by only O(n2log⁡n)\order{n^2\log n} 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 (n2−1)(n^2-1)-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.