The total number of nodes generated in a search or proof tree during an automated reasoning or proof-search procedure; each node represents a distinct subgoal, partial assignment, intermediate formula, or inference state.

Principle

Measures combinatorial branching and duplication in a search process: larger size typically reflects more branching, backtracking, or repeated exploration of similar states.

Demonstration

In a backtracking SAT solver, the search tree size counts every decision node and every implied propagation node encountered while exploring partial assignments until a satisfying assignment or refutation is found.

Misapplication

Treating search tree size as a direct proxy for wall-clock running time without accounting for per-node cost, parallelism, or memoization (DAG compression) can mislead algorithmic assessment.

Consequence

When properly measured, search tree size yields an upper bound on the number of inference steps or node-visits; exponential tree size implies potentially exponential runtime in worst-case sequential search.

Reversal

Instead of counting nodes, one could count only distinct states after value-based canonicalization (DAG size), which reduces counts by merging identical subproblems and inverts the measurement focus from exploration to reuse.

Boundary

Applies to tree-shaped exploration traces; it excludes costs internal to a node (e.g., expensive constraint propagation), does not capture DAG reuse unless nodes are merged, and depends on the granularity chosen for what constitutes a node.

Semantic Tension

Competes with measures like proof length and proof space: tree size emphasizes branching structure and duplication, whereas length counts sequential inferences and space measures memory footprint.

Synthesis

Search tree size is a combinatorial count that quantifies the extent of branching and redundant exploration in search; combined with per-node cost and reuse analysis it predicts practical difficulty and guides heuristics to reduce branching or enable merging.