Decision Tree Model¶

An adaptive query-complexity model represented by a tree of permitted tests and answer branches, with leaves as outputs and path length as query cost.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8885
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Computational Complexity, Query Complexity → Computer Science & Software Engineering
Aliases: Query model, Decision-tree model of computation, Decision tree complexity model

Core Idea¶

The decision tree model isolates the information an algorithm obtains from an input. Each internal node asks an allowed query, each answer selects a branch, and the reached leaf returns the algorithm's output.

Under unit query cost, worst-case complexity is maximum depth. Because correct leaves must distinguish relevant input classes, counting leaves, adversary arguments, and polynomial methods can prove lower bounds independent of implementation details.

How would you explain it like I'm…

The Yes-or-No Question Game

Think of the game where you guess an animal by asking yes-or-no questions. Each answer sends you down a different path until you reach the answer. The decision tree model looks at problems this way and counts how many questions you must ask in the worst case. Since there are only so many paths, you can even prove that nobody could always win with fewer questions.

The Question-Tree Count

The decision tree model is a way computer scientists study how much information a program needs to solve a problem. Picture a tree of questions: at each branch point the program asks one allowed question about the input, the answer picks which way to go, and at the end, a leaf, it gives its answer. The number of questions asked on the longest path is how hard the problem is in the worst case. Because the leaves have to tell apart all the inputs that need different answers, you can count how many leaves are needed and prove that some number of questions is always necessary. For example, finding one of eight possibilities with yes-or-no questions needs at least three questions, since two questions give only four possible endings.

Query Trees for Lower Bounds

The decision tree model is a model of computation that captures only the information an algorithm gathers about its input. Each internal node of the tree is an allowed query, such as comparing two elements, each possible answer leads to a child, and each leaf gives the algorithm's output. If every query costs one unit, the worst-case cost of the algorithm is the tree's maximum depth. The model is useful for proving lower bounds, facts that no algorithm of this kind can beat, because correct leaves must separate all input classes that need different outputs. Techniques such as counting leaves, adversary arguments, and polynomial methods give these bounds without depending on any programming details.

The decision tree model is a model of computation that isolates the information an algorithm obtains from its input. Each internal node represents an allowed query, each possible answer selects an outgoing branch, and the leaf reached determines the algorithm's output. Under unit cost per query, worst-case complexity equals the maximum depth of the tree. Because a correct tree's leaves must distinguish all input classes that require different outputs, one can derive lower bounds that hold regardless of implementation details. Standard techniques include counting leaves (a tree of bounded branching and depth d has limited leaves), adversary arguments that answer queries so as to delay a determination, and polynomial methods. The model's power comes from abstracting away everything except the queries, so its bounds apply to any algorithm limited to those queries.

Scope of Application¶

Algorithm analysis. Counts comparisons or oracle queries.
Complexity lower bounds. Limits every algorithm using a query type.
Property testing. Studies partial access to large inputs.
Randomized and quantum computing. Compares query models under distinct branching and error semantics.

Clarity¶

State deterministic, randomized, or quantum model; input promise; permitted query and outcomes; output relation; error allowance; cost convention; and whether free computation occurs between queries. Inclusion test: Specify the input set, allowed query type and outcomes, adaptive tree, leaf outputs, correctness condition, and worst-case, average, randomized, or quantum cost convention. Exclusion test: Exclude statistical decision-tree predictors, organizational decision diagrams, and algorithms whose dominant operations are not represented by the declared queries. Nearest boundary: A classification decision tree is a learned prediction model; a decision tree in complexity theory is an exact or bounded-error query model used to count information-gathering operations. Exit condition: It leaves the model when an algorithm obtains information through operations not encoded as permitted queries or cost includes undeclared computation between nodes. Common misclassifications: It is not a machine-learning decision tree. It does not count all computational work unless explicitly modeled. The query type is part of the model, not a cosmetic choice. Expected and worst-case depth are different measures. Nearest named distinctions: Classification tree: Learns predictive rules from data. Decision analysis tree: Represents choices, uncertainty, and utility. Binary search tree: Is a data structure. Branching program: May merge states into a DAG rather than a tree and uses different size measures.

Manages Complexity¶

The tree removes machine-level details and exposes only adaptive information acquisition, making algorithm-independent lower bounds possible.

Abstract Reasoning¶

Define the inputs, promise, and required outputs.
Choose the information queries allowed.
Represent adaptive transcripts as nodes and branches.
Prove every leaf is correct for its compatible inputs.
Measure paths and establish upper or lower bounds under the declared cost.

Knowledge Transfer¶

Decision-tree lower bounds transfer only when query power, error criterion, input promise, and cost model are preserved.

Neighborhood in Abstraction Space¶

Decision Tree Model sits in a moderately populated region (43^rd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Decision & System Modeling Frameworks (30 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08