A computation tree is a representation for the computation steps of a non-deterministic Turing machine

Non-deterministic Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....

 on a specified input. A computation tree

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

 is a rooted tree of nodes and edges. Each node in the tree represents a single computational state, while each edge represents a transition to the next possible computation. The number of nodes of the tree is the size of the tree and the length of the path from the root to a given node is the depth of the node. The largest depth of an output node is the depth of the tree. The output nodes of the tree are called leaves.

In a computation tree each output node is labeled Yes or No. If a tree, T, with an input space X, if and the path for x ends in node labeled yes, then the input x is accepted. Else it is rejected.

The depth of the computation tree for a given input is the computation time for the Turing machine on that input.

One of the primary methods of showing that a computational problem L is complete

Complete (complexity)

In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...

 for a given complexity class

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

C is to show that the computation tree of any algorithm in C can be directly analyzed in terms of L.